代码训练营第十五天（二叉树第二部分）

本文主要是介绍代码训练营第十五天（二叉树第二部分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树第二部分

深度优先用栈，广度优先用队列

层次遍历

102.二叉树的层序遍历(opens new window)

迭代

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null)return result;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()){//每一轮就是一层int len = queue.size();List<Integer> tempList = new ArrayList<>();while (len-- > 0){//len是每一层的结点的数量TreeNode temp = queue.poll();tempList.add(temp.val);if (temp.left != null)queue.offer(temp.left);if (temp.right != null)queue.offer(temp.right);}result.add(tempList);}return result;}
}

递归

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();lever(root, 0, result);return result;}private void lever(TreeNode root, int dept, List<List<Integer>> result){if (root == null)return;dept++;//深度增加，也就意味着result中会多一个元素，即多一层if (result.size() < dept){List<Integer> levelList = new ArrayList<>();result.add(levelList);}//下面的一行代码注意一定要放在外面// 因为前面的if是为了给数组开辟空间，并不是为了将val放入// 可能出现result.size() >= dept的情况，因为是递归result.get(dept - 1).add(root.val);lever(root.left,dept,result);lever(root.right,dept,result);}
}

107.二叉树的层次遍历II(opens new window)

就是之前的层次遍历多了一个反转数组

class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> result = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();if (root == null)return result;queue.offer(root);while (!queue.isEmpty()){List<Integer> tempList = new ArrayList<>();int len = queue.size();while (len-- > 0){TreeNode temp = queue.poll();tempList.add(temp.val);if (temp.left != null)queue.offer(temp.left);if (temp.right != null)queue.offer(temp.right);}result.add(tempList);}Collections.reverse(result);return result;}
}

199.二叉树的右视图(opens new window)

class Solution {public List<Integer> rightSideView(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();List<Integer> result = new ArrayList<>();if (root == null)return result;queue.offer(root);while (!queue.isEmpty()){int len = queue.size();while (len-- > 0){TreeNode treeNode = queue.poll();if (treeNode.left != null)queue.offer(treeNode.left);if (treeNode.right != null)queue.offer(treeNode.right);if(len == 0)result.add(treeNode.val);}}return result;}
}

637.二叉树的层平均值(opens new window)

class Solution {public List<Double> averageOfLevels(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();List<Double> result = new ArrayList<>();if (root == null)return result;queue.offer(root);while (!queue.isEmpty()){int len = queue.size();double sum = 0;double num = len;while (len-- > 0){TreeNode treeNode = queue.poll();sum += treeNode.val;if (treeNode.left != null)queue.offer(treeNode.left);if (treeNode.right != null)queue.offer(treeNode.right);}result.add(sum / num);}return result;}
}

429.N叉树的层序遍历(opens new window)

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

515.在每个树行中找最大值(opens new window)

class Solution {public List<Integer> largestValues(TreeNode root) {List<Integer> result = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();if (root == null)return  result;queue.offer(root);while (!queue.isEmpty()){int len = queue.size();int max = Integer.MIN_VALUE;while (len-- > 0){TreeNode temp = queue.poll();max = Math.max(max, temp.val);if (temp.left != null)queue.offer(temp.left);if (temp.right != null)queue.offer(temp.right);}result.add(max);}return result;}
}

116.填充每个节点的下一个右侧节点指针(opens new window)

迭代一

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

迭代二

class Solution {public Node connect(Node root) {if (root == null) {return root;}// 从根节点开始Node leftmost = root;while (leftmost.left != null) {// 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针Node head = leftmost;while (head != null) {head.left.next = head.right;if (head.next != null) {head.right.next = head.next.left;}// 指针向后移动head = head.next;}// 去下一层的最左的节点leftmost = leftmost.left;}return root;}
}

递归

在这里插入图片描述

class Solution {public Node connect(Node root) {dfs(root);return root;}private void dfs(Node root){if (root == null)return;Node left = root.left;Node right = root.right;while (left != null){//因为为完美二叉树，left为空就意味着树到底了left.next = right;//root的树内子孩子指向left = left.right;//两个孩子的子树的外部指向，右子树指向下一个的左子树right = right.left;}dfs(root.left);dfs(root.right);}
}

‘117.填充每个节点的下一个右侧节点指针II(opens new window)

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

104.二叉树的最大深度(opens new window)

深度优先

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;} else {int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return Math.max(leftHeight, rightHeight) + 1;}}
}

111.二叉树的最小深度

class Solution {public int minDepth(TreeNode root) {if(root == null) return 0;if(root.left == null && root.right == null) return 1;if(root.left == null) return minDepth(root.right) + 1;if(root.right == null) return minDepth(root.left) + 1;int m1 = minDepth(root.left);int m2 = minDepth(root.right);return Math.min(m1,m2) + 1; }
}

226.翻转二叉树

226. 翻转二叉树

题目

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

在这里插入图片描述

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

在这里插入图片描述

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

解答

正常递归

class Solution {public TreeNode invertTree(TreeNode root) {reverse(root);return root;}private void reverse(TreeNode root){if (root == null)return;TreeNode left = root.left;TreeNode right = root.right;root.left = right;root.right = left;if (root.left != null)reverse(root.left);if (root.right != null)reverse(root.right);}
}

101.对称二叉树

力扣题目链接

题目

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：

在这里插入图片描述

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

在这里插入图片描述

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

解答

注意递归是从root的两个子几点开始

class Solution {public boolean isSymmetric(TreeNode root) {return compare(root.left, root.right);}private boolean compare(TreeNode left, TreeNode right) {if (left == null && right != null) {return false;}if (left != null && right == null) {return false;}if (left == null && right == null) {return true;}if (left.val != right.val) {return false;}// 比较外侧boolean compareOutside = compare(left.left, right.right);// 比较内侧boolean compareInside = compare(left.right, right.left);return compareOutside && compareInside;}   
}
``