代码随想录训练营二刷第十五天 | 层序遍历10道 226.翻转二叉树 101.对称二叉树 2

代码随想录训练营二刷第十五天 | 层序遍历10道 226.翻转二叉树 101.对称二叉树 2

一、102. 二叉树的层序遍历

题目链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/
思路：两次while，内层控制每一行的数量，数量是添加的子节点的个数。

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {LinkedList<TreeNode> queue = new LinkedList<>();List<List<Integer>> result = new ArrayList<>();if (root == null) return result;queue.add(root);while (!queue.isEmpty()) {List<Integer> list = new ArrayList<>();int num = queue.size();while (num > 0) {TreeNode node = queue.poll();list.add(node.val);num--;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/
思路：正常的层序遍历，结束后翻转数组。

class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> arrayLists = new ArrayList<>();LinkedList<TreeNode> queue = new LinkedList<>();if (root == null) return arrayLists;queue.add(root);while (!queue.isEmpty()) {int len = queue.size();List<Integer> list = new ArrayList<>();while (len > 0) {TreeNode node = queue.poll();list.add(node.val);len--;if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}arrayLists.add(list);}int i = 0, j = arrayLists.size() - 1;while (i < j) {List<Integer> temp = arrayLists.get(i);arrayLists.set(i, arrayLists.get(j));arrayLists.set(j, temp);i++;j--;}return arrayLists;}
}

三、199. 二叉树的右视图

题目链接：https://leetcode.cn/problems/binary-tree-right-side-view/
思路：正常层序遍历，只有每层最后一个才加入结果集。

class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> list = new ArrayList<>();LinkedList<TreeNode> queue = new LinkedList<>();if (root == null) return list;queue.add(root);while (!queue.isEmpty()) {int len = queue.size();while (len > 0) {TreeNode node = queue.poll();if (len == 1) list.add(node.val);len--;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/
思路：正常层序遍历。

class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> list = new ArrayList<>();LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {int len = queue.size();Double sum = 0.0;for (int i = 0; i < len; i++) {TreeNode node = queue.poll();sum += node.val;if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}list.add(sum / len);}return list;}
}

五、429. N 叉树的层序遍历

题目链接：https://leetcode.cn/problems/n-ary-tree-level-order-traversal/
思路：常规层序遍历注意空指针。

class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> arrayLists = new ArrayList<>();LinkedList<Node> queue = new LinkedList<>();if (root == null) return arrayLists;queue.add(root);while (!queue.isEmpty()) {int len = queue.size();List<Integer> list = new ArrayList<>();for (int i = 0; i < len; i++) {Node node = queue.poll();list.add(node.val);for (Node child : node.children) {if (child != null) queue.add(child);}}arrayLists.add(list);}return arrayLists;}
}

六、515. 在每个树行中找最大值

题目链接：https://leetcode.cn/problems/find-largest-value-in-each-tree-row/
思路：正常层序遍历。

class Solution {public List<Integer> largestValues(TreeNode root) {List<Integer> list = new ArrayList<>();LinkedList<TreeNode> queue = new LinkedList<>();if (root == null) return list;queue.add(root);while (!queue.isEmpty()) {int len = queue.size(), max = Integer.MIN_VALUE;for (int i = 0; i < len; 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/
思路：层序遍历

class Solution {public Node connect(Node root) {if (root == null) return root;LinkedList<Node> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {int len = queue.size();while (len > 0) {Node node = queue.poll();if (len > 1) node.next = queue.peek();len--;if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}}return root;}
}

八、117. 填充每个节点的下一个右侧节点指针 II

题目链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/
思路：和上一题一样。

class Solution {public Node connect(Node root) {if (root == null) return root;LinkedList<Node> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {int len = queue.size();while (len > 0) {Node node = queue.poll();if (len > 1) node.next = queue.peek();len--;if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}}return root;}
}

九、104. 二叉树的最大深度

题目链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/
思路：层序遍历。

class Solution {public int maxDepth(TreeNode root) {if (root == null) return 0;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);int deep = 0;while (!queue.isEmpty()) {int len = queue.size();for (int i = 0; i < len; i++) {TreeNode node = queue.poll();if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}deep++;}return deep;}
}

十、111. 二叉树的最小深度

题目链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree/
思路：层序遍历提早返回。

class Solution {public int minDepth(TreeNode root) {if (root == null) return 0;LinkedList<TreeNode> queue = new LinkedList<>();int deep = 0;queue.add(root);while (!queue.isEmpty()) {int len = queue.size();for (int i = 0; i < len; i++) {TreeNode node = queue.poll();if (node.left == null && node.right == null) {return ++deep;}if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}deep++;}return deep;}
}

十一、226.翻转二叉树

题目链接：https://leetcode.cn/problems/invert-binary-tree/
思路：前序遍历交换

class Solution {public TreeNode invertTree(TreeNode root) {reserve(root);return root;}void reserve(TreeNode node) {if (node == null)return;TreeNode temp = node.left;node.left = node.right;node.right = temp;reserve(node.left);reserve(node.right);}
}

十二、101.对称二叉树 2

题目链接：https://leetcode.cn/problems/symmetric-tree/
思路：把一棵树分成两颗树进行比较

class Solution {boolean flag = true;public boolean isSymmetric(TreeNode root) {equal(root.left, root.right);return flag;}void equal(TreeNode node1, TreeNode node2) {if (node1 == null && node2 == null) {}else if (node1 != null && node2 != null) {if (node1.val != node2.val) {flag = false;}else {equal(node1.left, node2.right);equal(node1.right, node2.left);}}else {flag = false;}}
}