自己做的手工放在哪个网站卖,新余建站公司,软件自学网站,wordpress主题tint-k力扣爆刷第141天之二叉树十连刷#xff08;层序遍历#xff09; 文章目录 力扣爆刷第141天之二叉树十连刷#xff08;层序遍历#xff09;一、102. 二叉树的层序遍历二、107. 二叉树的层序遍历 II三、199. 二叉树的右视图四、637. 二叉树的层平均值五、429. N 叉树的层序遍…力扣爆刷第141天之二叉树十连刷层序遍历 文章目录 力扣爆刷第141天之二叉树十连刷层序遍历一、102. 二叉树的层序遍历二、107. 二叉树的层序遍历 II三、199. 二叉树的右视图四、637. 二叉树的层平均值五、429. N 叉树的层序遍历六、515. 在每个树行中找最大值七、116. 填充每个节点的下一个右侧节点指针八、117. 填充每个节点的下一个右侧节点指针 II九、104. 二叉树的最大深度十、111. 二叉树的最小深度 一、102. 二叉树的层序遍历
题目链接https://leetcode.cn/problems/binary-tree-level-order-traversal/description/ 思路层序遍历使用队列完成经典题目。通过队列size来控制层序遍历。
class Solution {ListListInteger result new ArrayList();public ListListInteger levelOrder(TreeNode root) {if(root null) return result;LinkedListTreeNode queue new LinkedList();queue.add(root);while(!queue.isEmpty()) {int size queue.size();ListInteger list new ArrayList();for(int i 0; i size; i) {TreeNode node queue.poll();list.add(node.val);if(node.left ! null) queue.add(node.left);if(node.right ! null) queue.add(node.right);}result.add(list);}return result;}
}二、107. 二叉树的层序遍历 II
题目链接https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/description/ 思路要求从叶子层到根节点层进行层序遍历直接层序遍历然后翻转数组。
class Solution {public ListListInteger levelOrderBottom(TreeNode root) {ListListInteger result new ArrayList();LinkedListTreeNode queue new LinkedList();if(root null) return result;queue.add(root);while(!queue.isEmpty()) {int size queue.size();ListInteger list new ArrayList();for(int i 0; i size; i) {TreeNode node queue.poll();list.add(node.val);if(node.left ! null) queue.add(node.left);if(node.right ! null) queue.add(node.right);}result.add(list);}int i 0, j result.size()-1;while(i j) {ListInteger t result.get(i);result.set(i, result.get(j));result.set(j, t);i;j--;}return result;}
}三、199. 二叉树的右视图
题目链接https://leetcode.cn/problems/binary-tree-right-side-view/description/ 思路本题可以直接层序遍历只需要在每一层遍历到size时记录数据。也可以直接前序遍历只不过遍历的顺序是右中左而且维护一个深度值只有每次突破深度时才记录。
class Solution {ListInteger list new ArrayList();public ListInteger rightSideView(TreeNode root) {if(root null) return list;LinkedListTreeNode queue new LinkedList();queue.add(root);while(!queue.isEmpty()) {int size queue.size();for(int i 0; i size; i) {TreeNode node queue.poll();if(i size-1) {list.add(node.val);}if(node.left ! null) queue.add(node.left);if(node.right ! null) queue.add(node.right);}}return list;}}四、637. 二叉树的层平均值
题目链接https://leetcode.cn/problems/average-of-levels-in-binary-tree/description/ 思路直接层序遍历然后收集每一层的总和利用size算平均值。
class Solution {public ListDouble averageOfLevels(TreeNode root) {ListDouble list new ArrayList();LinkedListTreeNode queue new LinkedList();queue.add(root);while(!queue.isEmpty()) {int size queue.size();double avg 0;for(int i 0; i size; i) {TreeNode node queue.poll();avg node.val;if(node.left ! null) queue.add(node.left);if(node.right ! null) queue.add(node.right);}list.add(avg/size);}return list;}
}五、429. N 叉树的层序遍历
题目链接https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/ 思路N叉树的层序遍历比二叉树来说只是多了几个叉不需要在直接写左右子树了直接一个for循环把子节点全遍历出来。
/*
// 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 result new ArrayList();if(root null) return result;LinkedListNode queue new LinkedList();queue.add(root);while(!queue.isEmpty()) {int size queue.size();ListInteger list new ArrayList();for(int i 0; i size; i) {Node node queue.poll();list.add(node.val);for(Node temp : node.children) {if(temp ! null) {queue.add(temp);}}}result.add(list);} return result;}
}六、515. 在每个树行中找最大值
题目链接https://leetcode.cn/problems/find-largest-value-in-each-tree-row/description/ 思路没啥东西就是层序遍历遍历每一层然后比较获取最大值。
/*** 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 list new ArrayList();if(root null) return list;LinkedListTreeNode queue new LinkedList();queue.add(root);while(!queue.isEmpty()) {int size queue.size();int max Integer.MIN_VALUE;for(int i 0; i size; i) {TreeNode node queue.poll();max Math.max(max, node.val);if(node.left ! null) queue.add(node.left);if(node.right ! null) queue.add(node.right);}list.add(max);}return list;}
}七、116. 填充每个节点的下一个右侧节点指针
题目链接https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/description/ 思路要求横向连接完美二叉树本题可以层序遍历遍历时先添加右子树再添加左子树。也可以使用递归递归的话每次递归传入左右两个节点然后让左节点指向右节点。
/*
// 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) {LinkedListNode queue new LinkedList();if(root null) return root;queue.add(root);while(!queue.isEmpty()) {int size queue.size();Node p null;for(int i 0; i size; i) {Node node queue.poll();node.next p;p node;if(node.right ! null) queue.add(node.right);if(node.left ! null) queue.add(node.left);}}return root;}}八、117. 填充每个节点的下一个右侧节点指针 II
题目链接https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/description/ 思路上一题是完全二叉树可以使用递归来做本题是普通二叉树使用层序遍历会简单很多具体解法和上一题一致。
/*
// 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) {if(root null) return root;LinkedListNode queue new LinkedList();queue.add(root);while(!queue.isEmpty()) {int size queue.size();Node p null;for(int i 0; i size; i) {Node node queue.poll();node.next p;p node;if(node.right ! null) queue.add(node.right);if(node.left ! null) queue.add(node.left);}}return root;}
}九、104. 二叉树的最大深度
题目链接https://leetcode.cn/problems/maximum-depth-of-binary-tree/ 思路本题还是使用递归吧后序遍历直接解决使用层序遍历只需要记录层的个数就可以大材小用了。
class Solution {public int maxDepth(TreeNode root) {if(root null) return 0;int left maxDepth(root.left);int right maxDepth(root.right);return Math.max(left, right) 1;}
}十、111. 二叉树的最小深度
题目链接https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/ 思路可以使用递归用一个全局变量记录最小深度然后在递归函数的参数中携带当前深度直接遍历就行了在叶子节点收集结果。 也可以层序遍历只需要在每一层层序遍历时记录叶子节点只要发现叶子节点即可返回。
class Solution {int min Integer.MAX_VALUE;public int minDepth(TreeNode root) {if(root null) return 0;fun(root, 1);return min;}void fun(TreeNode root, int v) {if(root null) return ;if(root.left null root.right null) {min Math.min(min, v);return ;}fun(root.left, v1);fun(root.right, v1);}
}
