LeetCode 解题思路 24（Hot 100）

解题思路：

1. 确定根节点： 前序遍历的第一个元素是当前子树的根节点。
2. ​分割中序数组： 在中序遍历中找到根节点的位置，其左侧为左子树的中序，右侧为右子树的中序。
3. 递归构造子树： 根据左子树的长度，分割前序数组，分别构造左子树和右子树。

Java代码：

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {Map<Integer, Integer> inorderMap = new HashMap<>();for (int i = 0; i < inorder.length; i++)inorderMap.put(inorder[i], i);return buildHelper(preorder, 0, preorder.length - 1,inorder, 0, inorder.length - 1,inorderMap);}private TreeNode buildHelper(int[] preorder, int preStart, int preEnd,int[] inorder, int inStart, int inEnd,Map<Integer, Integer> inorderMap) {if (preStart > preEnd || inStart > inEnd) return null;int rootVal = preorder[preStart];TreeNode root = new TreeNode(rootVal);int rootIndex = inorderMap.get(rootVal);int leftSize = rootIndex - inStart;root.left = buildHelper(preorder, preStart + 1, preStart + leftSize,inorder, inStart, rootIndex, inorderMap);root.right = buildHelper(preorder, preStart + leftSize + 1, preEnd,inorder, rootIndex + 1, inEnd, inorderMap);return root;}
}

复杂度分析：

• 时间复杂度： O(n)，每个节点仅被处理一次，哈希表查询时间为 O(1)，总共有 n 个节点。
• 空间复杂度： O(n)，递归栈的深度取决于树的高度，最坏情况下（链表树）为 O(n)。哈希表存储中序遍历的值到索引的映射，占用 O(n) 空间。

解题思路：

1. 前缀和与哈希表： 维护一个哈希表 prefixSum，记录从根节点到当前路径的前缀和及其出现次数。初始化时存入 {0: 1}，用于处理从根节点开始的路径。
2. 递归遍历： 对每个节点，计算当前前缀和 currentSum。检查是否存在 currentSum - targetSum 在哈希表中，若存在则累加对应次数到结果。将当前前缀和加入哈希表，递归处理左右子树，回溯时撤销当前前缀和的记录。
3. 路径灵活处理： 路径不需要从根开始或结束在叶子，但必须向下。通过哈希表动态维护当前路径的前缀和，确保路径连续性。

Java代码：

class Solution {private int result = 0;public int pathSum(TreeNode root, int targetSum) {Map<Long, Integer> prefixSum = new HashMap<>();prefixSum.put(0L, 1);dfs(root, 0, prefixSum, targetSum);return result;}private void dfs(TreeNode node, long currentSum, Map<Long, Integer> prefixSum, int targetSum) {if (node == null) return;currentSum += node.val;result += prefixSum.getOrDefault(currentSum - targetSum, 0);prefixSum.put(currentSum, prefixSum.getOrDefault(currentSum, 0) + 1);dfs(node.left, currentSum, prefixSum, targetSum);dfs(node.right, currentSum, prefixSum, targetSum);prefixSum.put(currentSum, prefixSum.get(currentSum) - 1);}
}

复杂度分析：

• 时间复杂度： O(n)，每个节点仅被访问一次，哈希表操作（插入、查询、删除）均为 O(1)。
• 空间复杂度： O(n)，递归栈的深度取决于树的高度 h（最坏情况为链状树，h = n）。O(n) 哈希表最多存储 n 个不同的前缀和（例如，当所有节点值唯一且路径和互不相同时）。