当前位置：首页 > news >正文

【LeetCode | 第六篇】算法笔记

news 2026/5/12 10:27:01

二叉树

二叉树二叉树展开为链表编辑

从前序与中序遍历序列构造二叉树编辑

路径总和 III

二叉树的最近公共祖先

二叉树中的最大路径和编辑

【LeetCode | 第五篇】算法笔记https://blog.csdn.net/h52412224/article/details/159043914

【LeetCode | 第四篇】算法笔记https://blog.csdn.net/h52412224/article/details/159018487【LeetCode | 第三篇】算法笔记https://blog.csdn.net/h52412224/article/details/158689782?spm=1001.2014.3001.5502【LeetCode | 第二篇】算法笔记https://blog.csdn.net/h52412224/article/details/158467673?spm=1001.2014.3001.5502【LeetCode | 第一篇】算法笔记https://blog.csdn.net/h52412224/article/details/157903186

二叉树

二叉树二叉树展开为链表

思路1：递归

class Solution { public void flatten(TreeNode root) { // 递归终止条件：空节点或叶子节点无需处理 if (root == null ) { return; } // 1. 递归展开左子树 flatten(root.left); // 2. 递归展开右子树 flatten(root.right); // 3. 保存原右子树（后续要接到左子树的最右侧） TreeNode tempRight = root.right; // 4. 将展开后的左子树移到右指针位置，左指针置空 root.right = root.left; root.left = null; // 5. 找到新右子树（原左子树）的最右侧节点 TreeNode current = root; while (current.right != null) { current = current.right; } // 6. 将原右子树接到最右侧节点的右指针上 current.right = tempRight; } }

思路2：递归后序

展开规则：原树 → 单链表，顺序为前序遍历，所有右指针串联，左指针为 null。
后序递归：先处理右子树，再处理左子树，最后处理根。
记录上一个节点，将当前节点右指针指向上一节点，左指针置空。

class Solution { private TreeNode prev = null; public void flatten(TreeNode root) { if (root == null) return; flatten(root.right); // 先右 flatten(root.left); // 再左 // 拼接 root.right = prev; root.left = null; prev = root; } }

从前序与中序遍历序列构造二叉树

思路：递归分治

前序遍历：根 → 左 → 右；中序遍历：左 → 根 → 右。
前序第一个节点为根，在中序中找到根的位置，划分左、右子树区间。
递归构建左、右子树，用哈希表快速定位根在中序的下标。

class Solution { private Map<Integer, Integer> inMap; public TreeNode buildTree(int[] preorder, int[] inorder) { inMap = new HashMap<>(); for (int i = 0; i < inorder.length; i++) { inMap.put(inorder[i], i); // 中序值→下标 } return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1); } // pre: [preL, preR], in: [inL, inR] private TreeNode build(int[] pre, int preL, int preR, int[] in, int inL, int inR) { if (preL > preR) return null; int rootVal = pre[preL]; // 前序首为根 TreeNode root = new TreeNode(rootVal); int mid = inMap.get(rootVal); // 中序根位置 int leftLen = mid - inL; // 左子树长度 // 递归左、右 root.left = build(pre, preL+1, preL+leftLen, in, inL, mid-1); root.right = build(pre, preL+leftLen+1, preR, in, mid+1, inR); return root; } }

路径总和 III

思路1：前缀和 +哈希表

路径为任意向下路径，用前缀和记录从根到当前节点的和。
哈希表存储前缀和出现次数，当前和 - 目标和 = 历史前缀和，次数即为路径数。
回溯：递归返回时移除当前前缀和，避免影响其他分支。

class Solution { private Map<Long, Integer> preMap; private int count; public int pathSum(TreeNode root, int targetSum) { preMap = new HashMap<>(); preMap.put(0L, 1); // 前缀和0出现1次 count = 0; dfs(root, 0, targetSum); return count; } private void dfs(TreeNode node, long sum, int target) { if (node == null) return; sum += node.val; // 查找历史前缀和 count += preMap.getOrDefault(sum - target, 0); preMap.put(sum, preMap.getOrDefault(sum, 0) + 1); dfs(node.left, sum, target); dfs(node.right, sum, target); // 回溯 preMap.put(sum, preMap.get(sum) - 1); } }

思路2：双重递归

外层递归遍历每个节点作为路径起点。
内层递归从起点向下，累加和，等于目标则计数。
时间复杂度 O (n²)，空间 O (h)。

class Solution { public int pathSum(TreeNode root, int targetSum) { if (root == null) return 0; // 当前节点为起点 + 左子树 + 右子树 return dfs(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum); } // 以node为起点，向下找路径 private int dfs(TreeNode node, long target) { if (node == null) return 0; int res = 0; if (node.val == target) res++; res += dfs(node.left, target - node.val); res += dfs(node.right, target - node.val); return res; } }

二叉树的最近公共祖先

思路1：递归

后序遍历：左、右、根。
若当前节点为 p/q，返回当前节点；若左右子树各找到一个，当前为祖先；否则返回找到的一侧。

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) { // 若未找到节点 p 或 q return null; }else if(left == null && right != null) { // 若找到一个节点 return right; }else if(left != null && right == null) { // 若找到一个节点 return left; }else { // 若找到两个节点 return root; } } }

二叉树中的最大路径和

思路：递归后序

路径可任意拐弯，最大路径 = 左贡献 + 根 + 右贡献。
递归返回当前节点向上的最大贡献（max (左，右)+ 根）。
全局变量记录遍历过程中的最大路径和。

class Solution { private int maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return maxSum; } private int dfs(TreeNode node) { if (node == null) { return 0; } // 计算左子树最大贡献值（若为负数则取0，舍弃该子树） int leftGain = Math.max(dfs(node.left), 0); // 计算右子树 int rightGain = Math.max(dfs(node.right), 0); // 计算以当前节点为顶点的路径和（左右子树都包含，是一个完整的路径） int currentPathSum = node.val + leftGain + rightGain; // 更新全局最大路径和 maxSum = Math.max(maxSum, currentPathSum); // 返回以当前节点为起点的最大贡献值（只能选左或右一个方向，因为路径是单向的） return node.val + Math.max(leftGain, rightGain); } }