网站开发面试题,外贸网站源码php,天津本地网站,网站引导页是什么1#xff0c;力扣102
给你二叉树的根节点 root #xff0c;返回其节点值的 层序遍历 。 #xff08;即逐层地#xff0c;从左到右访问所有节点#xff09;。 示例 1#xff1a; 输入#xff1a;root [3,9,20,null,null,15,7]
输出#xff1a;[[3],[9,20],[15,7]]示例…1力扣102
给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。 示例 1 输入root [3,9,20,null,null,15,7]
输出[[3],[9,20],[15,7]]示例 2
输入root [1]
输出[[1]]示例 3
输入root []
输出[]提示
树中节点数目在范围 [0, 2000] 内-1000 Node.val 1000
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger res new ArrayListListInteger();//二维数组存数据QueueTreeNodeque new LinkedListTreeNode();//借助队列if(rootnull) return res;que.offer(root);while(!que.isEmpty()){//遍历每一层int len que.size();//用于记录每一层节点的个数ListIntegerlist new ArrayList();while(len0){//对每一层数据进行处理TreeNode t que.poll();list.add(t.val);//收集一层数据if(t.left!null) que.offer(t.left);if(t.right!null) que.offer(t.right);len--;}res.add(list);//收集一整层数据}return res;}
}
2力扣107 二叉树遍历II
给你二叉树的根节点 root 返回其节点值 自底向上的层序遍历 。 即按从叶子节点所在层到根节点所在的层逐层从左向右遍历 示例 1 输入root [3,9,20,null,null,15,7]
输出[[15,7],[9,20],[3]]示例 2
输入root [1]
输出[[1]]示例 3
输入root []
输出[]提示
树中节点数目在范围 [0, 2000] 内-1000 Node.val 1000
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public ListListInteger levelOrderBottom(TreeNode root) {ListListInteger res new ArrayListListInteger();QueueTreeNode que new LinkedList();if(rootnull) return res;que.offer(root);while(!que.isEmpty()){int len que.size();ListIntegerlist new ArrayList();while(len 0){TreeNode t que.poll();list.add(t.val);if(t.left!null) que.offer(t.left);if(t.right!null) que.offer(t.right);len--;}res.add(list);}Collections.reverse(res);//将res逆置一下即可return res;}
}
3 力扣199
二叉树的右视图
给定一个二叉树的 根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。 示例 1: 输入: [1,2,3,null,5,null,4]
输出: [1,3,4]示例 2:
输入: [1,null,3]
输出: [1,3]示例 3:
输入: []
输出: []提示:
二叉树的节点个数的范围是 [0,100]-100 Node.val 100
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public ListInteger rightSideView(TreeNode root) {ListInteger res new ArrayList();QueueTreeNodeque new LinkedListTreeNode();//借助队列if(rootnull) return res;que.offer(root);while(!que.isEmpty()){//遍历每一层int len que.size();//用于记录每一层节点的个数while(len0){//对每一层数据进行处理TreeNode t que.poll();if(len1){res.add(t.val);//只收集每一层的最后一个节点的值}if(t.left!null) que.offer(t.left);if(t.right!null) que.offer(t.right);len--;}}return res;}
} 4力扣637 二叉树层的平均值
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。 示例 1 输入root [3,9,20,null,null,15,7]
输出[3.00000,14.50000,11.00000]
解释第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。示例 2: 输入root [3,9,20,15,7]
输出[3.00000,14.50000,11.00000]提示 树中节点数量在 [1, 104] 范围内-231 Node.val 231 - 1
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public ListDouble averageOfLevels(TreeNode root) {ListDouble res new ArrayList();QueueTreeNodeque new LinkedListTreeNode();//借助队列if(rootnull) return res;que.offer(root);while(!que.isEmpty()){//遍历每一层int len que.size();//用于记录每一层节点的个数int size len;//记录len,一会算平均值做分母double sum 0;while(len0){//对每一层数据进行处理TreeNode t que.poll();sumt.val;if(t.left!null) que.offer(t.left);if(t.right!null) que.offer(t.right);len--;}double ave sum/size;res.add(ave);}return res;}
}
5 力扣429 N叉树的层序遍历 给定一个 N 叉树返回其节点值的层序遍历。即从左到右逐层遍历。
树的序列化输入是用层序遍历每组子节点都由 null 值分隔参见示例。 示例 1 输入root [1,null,3,2,4,null,5,6]
输出[[1],[3,2,4],[5,6]]示例 2 输入root [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]提示
树的高度不会超过 1000树的节点总数在 [0, 10^4] 之间 /*
// Definition for a Node.
class Node {public int val;public ListNode children;public Node() {}public Node(int _val) {val _val;}public Node(int _val, ListNode _children) {val _val;children _children;}
};
*/class Solution {public ListListInteger levelOrder(Node root) {ListListInteger res new ArrayListListInteger();//二维数组存数据QueueNodeque new LinkedListNode();//借助队列if(rootnull) return res;que.offer(root);while(!que.isEmpty()){//遍历每一层int len que.size();//用于记录每一层节点的个数ListIntegerlist new ArrayList();while(len0){//对每一层数据进行处理Node t que.poll();list.add(t.val);//收集一层数据for(Node child : t.children){//把每个节点的孩子都送进队列que.offer(child);}len--;}res.add(list);//收集一整层数据}return res;}
}
5 力扣515 找每个树行的最大值 给定一棵二叉树的根节点 root 请找出该二叉树中每一层的最大值。 示例1 输入: root [1,3,2,5,3,null,9]
输出: [1,3,9]示例2
输入: root [1,2,3]
输出: [1,3]提示
二叉树的节点个数的范围是 [0,104]-231 Node.val 231 - 1
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public ListInteger largestValues(TreeNode root) {ListInteger res new ArrayList();QueueTreeNodeque new LinkedListTreeNode();//借助队列if(rootnull) return res;que.offer(root);while(!que.isEmpty()){//遍历每一层int len que.size();//用于记录每一层节点的个数 int max Integer.MIN_VALUE; //使用这种初始化方式的场景通常出现在需要通过比较来找到一个数列中的最大值时 while(len0){//对每一层数据进行处理TreeNode t que.poll();if(t.val max){max t.val;}if(t.left!null) que.offer(t.left);if(t.right!null) que.offer(t.right);len--;}res.add(max);//收集一整层数据}return res;}
}
6填充每个节点的下一个右侧节点指针
116.填充每个节点的下一个右侧节点指针
力扣题目链接(opens new window)
给定一个完美二叉树其所有叶子节点都在同一层每个父节点都有两个子节点。二叉树定义如下
struct Node {int val;Node *left;Node *right;Node *next;
}1 2 3 4 5 6
填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL。
初始状态下所有 next 指针都被设置为 NULL。 /*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val _val;}public Node(int _val, Node _left, Node _right, Node _next) {val _val;left _left;right _right;next _next;}
};
*/class Solution {public Node connect(Node root) {QueueNodeque new LinkedListNode();//借助队列if(rootnull) return root;que.offer(root);while(!que.isEmpty()){//遍历每一层int len que.size();//用于记录每一层节点的个数while(len0){//对每一层数据进行处理Node t que.poll();Node tnext que.peek();//记录t的下一个节点if(len1){//每一层的最后一个节点之后没有节点t.next null;}else{//后面有节点则指向后节点t.next tnext;}if(t.left!null) que.offer(t.left);if(t.right!null) que.offer(t.right);len--;}}return root;}
}
7104.二叉树的最大深度
104.二叉树的最大深度
力扣题目链接(opens new window)
给定一个二叉树找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例
给定二叉树 [3,9,20,null,null,15,7] 返回它的最大深度 3 。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
//法一
class Solution {public int maxDepth(TreeNode root) {if(rootnull) return 0;QueueTreeNodeque new LinkedListTreeNode();//借助队列que.offer(root);int depth0;//记录深度初始化为0while(!que.isEmpty()){//遍历每一层int len que.size();//用于记录每一层节点的个数ListIntegerlist new ArrayList();while(len0){//对每一层数据进行处理TreeNode t que.poll();list.add(t.val);//收集一层数据if(t.left!null) que.offer(t.left);if(t.right!null) que.offer(t.right);len--;}depth;//一次遍历完深度加1}return depth;}
}
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
//法二递归
class Solution {public int maxDepth(TreeNode root) {if(root null) return 0;return 1Math.max(maxDepth(root.left),maxDepth(root.right));}
}
8力扣111 给定一个二叉树找出其最小深度
给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明叶子节点是指没有子节点的节点。 示例 1 输入root [3,9,20,null,null,15,7]
输出2示例 2
输入root [2,null,3,null,4,null,5,null,6]
输出5提示
树中节点数的范围在 [0, 105] 内-1000 Node.val 1000
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public int minDepth(TreeNode root) {QueueTreeNodeque new LinkedListTreeNode();//借助队列if(rootnull) return 0;que.offer(root);int depth 0;while(!que.isEmpty()){//遍历每一层int len que.size();//用于记录每一层节点的个数depth;//注意这里先深度加一不能在第二个循环之后因为万一就一个节点就会在下面depth返回出来为0是错的while(len0){//对每一层数据进行处理TreeNode t que.poll();if(t.left!null) que.offer(t.left);if(t.right!null) que.offer(t.right);if(t.leftnullt.rightnull){return depth;}len--;}}return depth;}
}
