【代码随想录】第六章-二叉树1
第六章 二叉树1
1 二叉树的层序遍历
102. 二叉树的层序遍历
给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
思路：
用Q.size()记录当前层节点的数量，遍历即可
java">class Solution {List<List<Integer>> list=new ArrayList<>();public List<List<Integer>> levelOrder(TreeNode root) {Deque<TreeNode> Q=new ArrayDeque<>();if(root==null) return list;TreeNode p=root;Q.add(p);while(!Q.isEmpty()){int levelSize = Q.size(); List<Integer> level = new ArrayList<>();for (int i = 0; i < levelSize; i++) {p = Q.poll();level.add(p.val);if (p.left != null) {Q.add(p.left);}if (p.right != null) {Q.add(p.right);}}list.add(level); }return list;}
}
107.二叉树的层序遍历II
给你二叉树的根节点root，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。
输入：root = [3,9,20,null,null,15,7] 输出：[[15,7],[9,20],[3]]
思路：
list.addFirst(level);使用头插即可
199.二叉树的右视图
给定一个二叉树的根节点root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
输入：root = [1,2,3,null,5,null,4] 输出：[1,3,4]
思路：
只用将每层的最后一个元素的val值加入list集合即可
637.二叉树的层平均值
给定一个非空二叉树的根节点root,以数组的形式返回每一层节点的平均值。与实际答案相差10-5以内的答案可以被接受。
输入：root = [3,9,20,null,null,15,7] 输出：[3.00000,14.50000,11.00000]
思路：
与之前思路一致
429.N叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
输入：root = [1,null,3,2,4,null,5,6] 输出：[[1],[3,2,4],[5,6]]
思路：
层序遍历，无非以前是两个，现在是一串
515.在每个树行中找最大值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
输入：root = [1,3,2,5,3,null,9] 输出：[1,3,9]
思路：
与之前思路一致
116.填充每个节点的下一个右侧节点指针
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。填充它的每个next指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将next指针设置为NULL。初始状态下，所有next指针都被设置为NULL。
输入：root = [1,2,3,4,5,6,7] 输出：[1,#,2,3,#,4,5,6,7,#]
思路：
存好之前的指针，分别进行处理即可
117.填充每个节点的下一个右侧节点指针II
104.二叉树的最大深度
给定一个二叉树root，返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
输入：root = [3,9,20,null,null,15,7] 输出：3
思路：
如果节点为空，深度为 0；如果左子树为空，递归计算右子树的深度；如果右子树为空，递归计算左子树的深度；如果左右子树都不为空，递归计算左右子树的深度
java">class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}if (root.left == null) {return maxDepth(root.right) + 1;}if (root.right == null) {return maxDepth(root.left) + 1;}int leftDepth = maxDepth(root.left);int rightDepth = maxDepth(root.right);return Math.max(leftDepth, rightDepth) + 1;}
}
559.N叉树的最大深度
给定一个N叉树，找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
输入：root = [1,null,3,2,4,null,5,6] 输出：3
思路：
如果根节点是 null，直接返回深度为 0；如果当前节点的 children 为空或 children.isEmpty() 为 true，说明它是叶子节点，深度为 1；遍历当前节点的所有子节点，递归计算每个子节点的深度。用 Math.max 维护所有子树的最大深度；当前节点的深度等于子树最大深度加 1。
java">class Solution {public int maxDepth(Node root) {if (root == null) return 0;if(root.children == null || root.children.isEmpty()) return 1; int maxDepth = 0;for (Node child : root.children) {maxDepth = Math.max(maxDepth, maxDepth(child));}return maxDepth + 1;}
}
111.二叉树的最小深度
给定一个二叉树root，返回其最大深度。二叉树的最小深度是指从根节点到最远叶子节点的最短路径上的节点数。
输入：root = [3,9,20,null,null,15,7] 输出：2
思路：
如果节点为空，深度为 0；如果左子树为空，递归计算右子树的深度；如果右子树为空，递归计算左子树的深度；如果左右子树都不为空，递归计算左右子树的深度。改为Math.min即可。
2 翻转二叉树
226.翻转二叉树
给你一棵二叉树的根节点root，翻转这棵二叉树，并返回其根节点。
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
思路：
先序遍历，把输出改为交换节点的操作
java">class Solution {public TreeNode invertTree(TreeNode root) {if(root!=null){TreeNode temp=root.left;root.left=root.right;root.right=temp;invertTree(root.left);invertTree(root.right);}return root;}
}
3 对称二叉树
101.对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
输入：root = [1,2,2,3,4,4,3] 输出：true
思路：
递归遍历
java">class Solution {public boolean isSymmetric(TreeNode root) {if (root == null) return true;return isSym(root.left, root.right);} public boolean isSym(TreeNode node1, TreeNode node2) {if (node1 == null && node2 == null) return true;if (node1 == null || node2 == null || node1.val != node2.val) {return false;}return isSym(node1.left, node2.right) && isSym(node1.right, node2.left);}
}
100.相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
输入：p = [1,2,3], q = [1,2,3] 输出：true
思路：
递归遍历
java">class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p==null&&q==null) return true;if(p==null||q==null) return false;if(p!=null&&q!=null&&q.val!=p.val) return false;return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right); }
}
572.另一棵树的子树
给你两棵二叉树root和subRoot。检验root中是否包含和subRoot具有相同结构和节点值的子树。如果存在，返回true；否则，返回false。二叉树tree的一棵子树包括tree的某个节点和这个节点的所有后代节点。tree也可以看做它自身的一棵子树。
输入：root = [3,4,5,1,2], subRoot = [4,1,2] 输出：true
思路：
如果subRoot为null，说明它是任何树的子树，直接返回true；如果root为null，说明主树为空，不可能包含子树，返回false。
如果当前节点值匹配（root.val==subRoot.val），则调用辅助函数isSameTree判断两棵树是否完全相同。如果当前节点值不匹配，递归判断subRoot是否为root.left或root.right的子树。
java">class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if (subRoot == null) return true; if (root == null) return false; if (root.val == subRoot.val && isSameTree(root, subRoot)) {return true;}return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);}private boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) return true;if (p == null || q == null) return false;if (p.val != q.val) return false;return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}
}
4 完全二叉树的节点个数
222.完全二叉树的节点个数
给出一个完全二叉树，求出该树的节点个数。
输入：root = [1,2,3,4,5,6] 输出：6
思路：
递归遍历
java">class Solution {public int countNodes(TreeNode root) {if(root == null) return 0;return countNodes(root.left) + countNodes(root.right) + 1;}
}
5 平衡二叉树
110.平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。
输入：root = [3,9,20,null,null,15,7] 输出：true
思路：
Method1：全局变量
只有flag为true时才修改。否则不动flag，后序遍历求树高。
java">class Solution {boolean flag = true;public boolean isBalanced(TreeNode root) {findDepth(root);return flag;}public int findDepth(TreeNode root) {int hl, hr;if (root != null) {hl = findDepth(root.left);hr = findDepth(root.right);if (flag) {flag = Math.abs(hl - hr) <= 1;}return Math.max(hl, hr) + 1;} else {return 0;}}
}
Method2：快速返回
通过调用 findDepth 方法，如果返回值为 -1，表示树不平衡；否则树平衡，对于空节点，深度直接返回 0，递归计算左子树深度，如果左子树已经不平衡，直接返回 -1，终止后续计算（剪枝优化）。同样，递归计算右子树深度，提前剪枝。判断当前节点是否平衡，如果左右子树深度差超过 1，返回 -1。如果当前节点平衡，返回以该节点为根的子树的深度。
java">class Solution {public boolean isBalanced(TreeNode root) {return findDepth(root) != -1; }public int findDepth(TreeNode root) {if (root == null) return 0;int leftDepth = findDepth(root.left);if (leftDepth == -1) return -1;int rightDepth = findDepth(root.right);if (rightDepth == -1) return -1;if (Math.abs(leftDepth - rightDepth) > 1) return -1;return Math.max(leftDepth, rightDepth) + 1;}
}
6 二叉树的所有路径
257.二叉树的所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。
输入：root = [3,9,20,null,null,15,7] 输出：true
思路：
回溯递归
java">class Solution {List<String> list = new ArrayList<>();public List<String> binaryTreePaths(TreeNode root) {if (root == null) {return list;}List<Integer> level = new ArrayList<>();level.add(root.val);dfs(root, level);return list;}public void dfs(TreeNode root, List<Integer> level) {if (root.left == null && root.right == null) {StringBuilder sb = new StringBuilder();for (Integer s : level) {sb.append(String.valueOf(s)).append("->");}if (sb.length() > 0) {sb.setLength(sb.length() - 2);}list.add(sb.toString());return;}if (root.left != null) {level.add(root.left.val);dfs(root.left, level);level.remove(level.size() - 1);}if (root.right != null) {level.add(root.right.val);dfs(root.right, level);level.remove(level.size() - 1);}return;}
}
7 左叶子之和
404.左叶子之和
计算给定二叉树的所有左叶子之和。
输入：root = [3,9,20,null,null,15,7] 输出：24
思路：
只有从左孩子分支进去的节点的左右孩子为空才将其值加入到sum中，否则继续遍历。
java">class Solution {int sum=0;public int sumOfLeftLeaves(TreeNode root) {if(root==null){return sum+0;}if(root.left!=null){sumOfLeftLeaves(root.left);if(root.left.left==null&&root.left.right==null){sum+=root.left.val;}}if(root.right!=null){sumOfLeftLeaves(root.right);}return sum;}
}
8 找树左下角的值
513.找树左下角的值
给定一个二叉树，在树的最后一行找到最左边的值。
输入： root = [2,1,3] 输出：1
思路：
Method1：递归法-先序遍历求二叉树高度
先遍历左子树，再遍历右子树，在遍历的过程中，如果更新了最大高度，那么一定是当前最左下的叶子节点
java">class Solution {private int Deep = -1;private int value = 0;public int findBottomLeftValue(TreeNode root) {value = root.val;findLeftValue(root,0);return value;}private void findLeftValue (TreeNode root,int deep) {if(root!=null){if(deep>Deep){Deep=deep;value=root.val;}findLeftValue(root.left,deep+1);findLeftValue(root.right,deep+1);}}
}
Method2：迭代层序遍历
迭代层序遍历，输出每层第一个
java">class Solution {public int findBottomLeftValue(TreeNode root) {Deque<TreeNode> queue = new ArrayDeque<>();queue.add(root);int res = 0;while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode poll = queue.poll();if (i == 0) res = poll.val;if (poll.left != null) {queue.add(poll.left);}if (poll.right != null) {queue.add(poll.right);}}}return res;}
}
