hot100 二叉树专题

1 二叉树的中序遍历class Solution { public ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); traversal(root, res); return res; } public void traversal(TreeNode root, ListInteger res) { if(root null) return; traversal(root.left, res); res.add(root.val); traversal(root.right, res); } }递归中序遍历即可。2 二叉树的最大深度后续遍历递归处理class Solution { public int maxDepth(TreeNode root) { if(root null) return 0; int leftDepth maxDepth(root.left); int rightDepth maxDepth(root.right); return Math.max(leftDepth, rightDepth) 1; } }3 翻转二叉树写一个翻转工具函数然后在主函数中按先序遍历或者后序遍历的顺序来处理即可二刷感悟不能用中序遍历来处理否则会出错。用后序或者先序。class Solution { public TreeNode invertTree(TreeNode root) { if(root null) return root; swap(root); invertTree(root.left); invertTree(root.right); return root; } private void swap(TreeNode root) { TreeNode temp root.left; root.left root.right; root.right temp; } }4 对称二叉树写一个compare函数传入两个节点left 、 right考虑各种情况left null right nullleft ! null right nullleft null right ! nullleft.val ! eight.val;最后递归比较compare(left.right, right.left)compare(left.left, right.right);返回递归结果的inside outsideclass 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 true; else if (left null right ! null) return false; else if (left ! null right null) return false; else if (left.val ! right.val) return false; boolean inside compare(left.right, right.left); boolean outside compare(left.left, right.right); return inside outside; } }5 二叉树的直径直径的本质某个节点的「左子树最大深度」 「右子树最大深度」的最大值因为直径路径必然经过某个节点以该节点为 “中点” 向左右延伸递归计算每个节点的左右子树最大深度遍历所有节点记录「左深度 右深度」的最大值即直径该过程仍基于后序遍历先算子树深度再算当前节点的直径贡献。class Solution { // 全局变量记录二叉树的最大直径边数 private int maxDiameter 0; public int diameterOfBinaryTree(TreeNode root) { // 空树直径为0 if (root null) { return 0; } // 递归计算每个节点的深度同时更新最大直径 calculateDepth(root); // 返回最终的最大直径 return maxDiameter; } /** * 后序遍历计算节点的最大深度同时更新全局最大直径 * param node 当前节点 * return 当前节点的最大深度节点数 */ private int calculateDepth(TreeNode node) { // 递归终止条件空节点深度为0 if (node null) { return 0; } // 1. 后序遍历先算左子树深度左 int leftDepth calculateDepth(node.left); // 2. 后序遍历再算右子树深度右 int rightDepth calculateDepth(node.right); // 3. 后序遍历处理当前节点根 // 当前节点的直径贡献 左深度 右深度边数 // 对比并更新全局最大直径 maxDiameter Math.max(maxDiameter, leftDepth rightDepth); // 返回当前节点的最大深度节点数左右子树深度最大值 1当前节点 return Math.max(leftDepth, rightDepth) 1; } }6 层序遍历层序遍历的题目就是模板题目熟悉即可熟练应用。class Solution { public ListListInteger levelOrder(TreeNode root) { ListListInteger res new ArrayList(); if(root null) return res; QueueTreeNode que new LinkedList(); que.offer(root); while (!que.isEmpty()) { int size que.size(); ListInteger path new LinkedList(); for (int i 0; i size; i) { TreeNode cur que.poll(); path.add(cur.val); if (cur.left ! null) que.offer(cur.left); if (cur.right ! null) que.offer(cur.right); } res.add(path); } return res; } }7 将有序数组转换为二叉搜索树写一个函数传入nums, left, right;如果left right return null;计算mid取出数组对应下标的元素作为新节点的值。root.left buildBST(nums, left, mid - 1);root.right buildBST(nums, mid 1, right);/** * 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 TreeNode sortedArrayToBST(int[] nums) { TreeNode root buildBST(nums, 0, nums.length - 1); return root; } public TreeNode buildBST(int[] nums, int left, int right) { if (left right) return null; int mid (left right) / 2; TreeNode root new TreeNode(nums[mid]); root.left buildBST(nums, left, mid - 1); root.right buildBST(nums, mid 1, right); return root; } }8 验证二叉搜索树要点中序遍历leftValid false 可提前剪枝pre用于记录中序遍历序列里前一个元素最后rightValid就是最后的结果返回class Solution { // 全局/成员变量记录中序遍历的前一个节点 private TreeNode pre; public boolean isValidBST(TreeNode root) { // 递归终止条件空树是合法的BST if(root null) return true; // 1. 中序遍历先递归检查左子树左 boolean leftValid isValidBST(root.left); // 左子树不合法直接返回false剪枝无需后续判断 if (!leftValid) { return false; } // 2. 中序遍历处理当前节点根 // 若前一个节点不为空且当前节点值 ≤ 前一个节点值 → 违反递增规则不是BST if (pre ! null root.val pre.val) { return false; } // 更新前一个节点为当前节点供后续右子树对比 pre root; // 3. 中序遍历递归检查右子树右 boolean rightValid isValidBST(root.right); // 右子树的结果就是当前层的结果 return rightValid; } }9 二叉搜索树中第K小的元素利用 BST 中序遍历递增的特性计数到第 k 个节点时记录值提前终止递归减少无效计算class Solution { int curNum 1; int res 0; public int kthSmallest(TreeNode root, int k) { traversal(root, k); return res; } public void traversal(TreeNode root, int k) { // 递归终止空节点 或 已找到第k小元素 if (root null || curNum k) return; // 中序遍历左 traversal(root.left, k); // 仅在curNumk时处理避免多余赋值 if (curNum k) { res root.val; } // 仅在curNumk时计数避免curNum无意义增长 if (curNum k) { curNum; } // 中序遍历右 traversal(root.right, k); } }10 二叉树的右视图层序遍历模板题/** * 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(); if(root null) return res; QueueTreeNode que new LinkedList(); que.offer(root); while(!que.isEmpty()) { int size que.size(); for(int i 0; i size; i) { TreeNode node que.poll(); if(node.left ! null) que.offer(node.left); if(node.right ! null) que.offer(node.right); if(i size - 1) { res.add(node.val); } } } return res; } }11 把二叉树展开为链表前序遍历用right节点来保存root.right,避免后续递归被覆盖用pre来保存前一个节点遍历到root的时候如果root不为空则给pre.left和root.right赋值pre root递归root的root.left以及原本的right。class Solution { TreeNode pre null; public void flatten(TreeNode root) { if (root null) return; TreeNode right root.right; if (pre ! null) { pre.right root; pre.left null; } pre root; flatten(root.left); flatten(right); } }二刷下面这种方法更好理解class Solution { public void flatten(TreeNode root) { if (root null) return; // 先展开左右子树 flatten(root.left); flatten(root.right); // 保存原来的右子树 TreeNode right root.right; // 左子树挪到右边 root.right root.left; root.left null; // 找到现在右链的最后一个节点 TreeNode cur root; while (cur.right ! null) { cur cur.right; } // 把原来的右子树接上 cur.right right; } }12 从前序遍历和中序遍历构造二叉树定义两个成员变量preIdx用于指示根节点的位置 map用于映射inorder[i]和i的关系便于后面使用。写一个工具函数treehelper根据preIdx找到根节点新建一个节点根据map找到rootval对应的下标index递归调用treeHelper分成左半部分和右半部分。class Solution { private int preIdx; private HashMapInteger, Integer map new HashMap(); public TreeNode buildTree(int[] preorder, int[] inorder) { preIdx 0; int len inorder.length; for (int i 0; i len; i) { map.put(inorder[i], i); } TreeNode root treeHelper(preorder, inorder, 0, len - 1); return root; } public TreeNode treeHelper(int[] preorder, int[] inorder, int inLeft, int inRight) { if (inLeft inRight) return null; int rootVal preorder[preIdx]; TreeNode root new TreeNode(rootVal); int index map.get(rootVal); root.left treeHelper(preorder, inorder, inLeft, index - 1); root.right treeHelper(preorder, inorder, index 1, inRight); return root; } }13 路径总和Ⅲ要回顾每个节点遍历到就先算自己的前缀和查map里有没有curSum - target有多少就是当前节点能贡献的路径数把自己的前缀和存进map让子节点能查到递归处理完左右子节点后把自己的前缀和从map里删掉回溯然后返回累计的路径数。二刷前缀和的思路sum - target 我们要找的 “历史前缀和”要用前序遍历因为前序遍历是一条路走到黑再回溯的符合题目的从上往下的原则。sum是值传递遍历保存在递归调用栈里面不需要手动回溯。只需要处理map。class Solution { // 哈希表key前缀和value该前缀和出现的次数 private HashMapLong, Integer prefixSumMap new HashMap(); private int target; public int pathSum(TreeNode root, int targetSum) { target targetSum; // 初始化前缀和为0的路径出现1次处理从根节点开始的路径 prefixSumMap.put(0L, 1); // 递归计算所有路径 return dfs(root, 0L); } // 递归回溯返回以当前节点为终点的符合条件的路径数 private int dfs(TreeNode node, long currSum) { if (node null) return 0; // 1. 计算当前节点的前缀和 currSum node.val; // 2. 核心找到符合条件的路径数 map中(currSum - target)的次数 int res prefixSumMap.getOrDefault(currSum - target, 0); // 3. 将当前前缀和存入map计数1 prefixSumMap.put(currSum, prefixSumMap.getOrDefault(currSum, 0) 1); // 4. 递归遍历左右子树累加结果 res dfs(node.left, currSum); res dfs(node.right, currSum); // 5. 回溯移除当前前缀和恢复map状态不影响其他分支 prefixSumMap.put(currSum, prefixSumMap.get(currSum) - 1); return res; } }14 二叉树的最近公共祖先后序遍历递归出口若当前节点为空 → 无节点可匹配返回 null若当前节点是 p 或 q → 找到目标节点返回当前节点告诉父节点“我这里找到了目标”。递归遍历左子树返回值 left左子树中找到的 p/q 节点或 null递归遍历右子树返回值 right右子树中找到的 p/q 节点或 null。左、右都非空 → p 和 q 分别在当前节点的左右子树 → 当前节点是最低公共祖先再往下找就只能包含一个目标了只有左非空 → 两个目标都在左子树 → 返回左子树的结果继续向上传递只有右非空 → 两个目标都在右子树 → 返回右子树的结果都为空 → 子树无目标返回 null。class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root null || root p || root q) { return root; } TreeNode left lowestCommonAncestor(root.left, p, q); TreeNode right lowestCommonAncestor(root.right, p, q); if (left ! null right ! null) { return root; }else if (left ! null right null) { return left; }else if (left null right ! null) { return right; }else { return null; } } }15 二叉树中的最大路径和后序遍历先处理左、右子树再处理当前节点符合 “从下往上计算路径和” 的需求递归时先舍弃负贡献的子树取 0计算当前节点作为最高点的路径和更新全局最大值返回值仅保留 “当前节点 左 / 右最大分支”向下延伸的路径和路径和的目标是 “最大化”如果某个子树的返回值是负数比如子树和为 - 5选择这个子树会让总路径和减少比如当前节点值为 3选 - 5 的话总和是 - 2不如不选总和为 3。用 Math.max(子树返回值, 0) 实现 “负贡献舍弃”本质是如果子树拖后腿就直接忽略这个子树。二刷左子树的最大值和右子树最大值需要和0取最大值0就表示不取左子树或者右子树。res全局更新leftVal rightVal root.val和res取最大值递归函数返回root.val Math.max(leftVal, rightVal)表示以当前节点为起点向下走的最大单链和不能同时走左右。class Solution { int res Integer.MIN_VALUE; // 全局最大路径和初始为最小整数处理全负数场景 public int maxPathSum(TreeNode root) { traversal(root); // 启动后序遍历 return res; // 最终返回全局最大值 } // 递归方法返回「从当前节点向下延伸的最大路径和」仅选左/右一个分支 public int traversal(TreeNode root) { // 步骤1递归终止条件空节点贡献为0 if (root null) return 0; // 步骤2后序遍历——先处理左、右子树舍弃负贡献的子树 // 核心如果子树返回值0选它会拉低路径和直接取0相当于不选该子树 int leftSum Math.max(traversal(root.left), 0); // 左子树向下延伸的最大和非负 int rightSum Math.max(traversal(root.right), 0); // 右子树向下延伸的最大和非负 // 步骤3计算「当前节点为最高点」的路径和形态1更新全局最大值 // 这个路径和 当前节点值 左子树贡献 右子树贡献拐点路径 int curMax root.val leftSum rightSum; res Math.max(res, curMax); // 全局最大值取“历史最大值”和“当前拐点路径和”的较大者 // 步骤4返回「当前节点向下延伸的最大路径和」形态2供父节点使用 // 只能选左/右其中一个分支因为父节点作为拐点时路径不能同时走当前节点的左右分支 return root.val Math.max(leftSum, rightSum); } }