🌲 路径与祖先：二叉树中的深度追踪技巧（LeetCode 437 / 236）

在二叉树的解题过程中，有一类问题聚焦于路径总和查找和节点之间的祖先关系，它们不仅考察遍历技巧，更锻炼我们对递归路径与状态传递的深刻理解。本篇我们将通过两道经典题目：路径总和 III 与最近公共祖先，逐步拆解思路与实现方式。

1️⃣ LeetCode 437. 路径总和 III

🧩 题目描述

给定一棵二叉树和一个整数 targetSum，返回路径总和等于该值的路径数量。路径不需要从根节点开始，也不需要在叶子节点结束，但路径方向必须向下（只能从父节点到子节点）。

🧠 思路一：双递归暴力解法（DFS）

我们可以遍历树中每个节点，以每个节点为起点，尝试向下查找所有路径和是否等于 targetSum，使用两层递归。

✅ 实现代码：

func pathSum(root *TreeNode, targetSum int) int {
   
    if root == nil {
   
        return 0
    }
    return dfs(root, targetSum) + pathSum(root.Left, targetSum) + pathSum(root.Right, targetSum)
}

// 以当前节点为起点，查找路径数
func dfs(node *TreeNode, target int) int {
   
    if node == nil {
   
        return 0
    }
    count := 0
    if node.Val == target {
   
        count++
    }
    count += dfs(node.Left, target - node.Val)
    count += dfs(node.Right, target - node.Val)
    return count
}

💡 思路二：前缀和 + 哈希优化（推荐）

利用前缀和思想，记录从根节点到当前节点的路径和，用哈希表记录每个前缀和出现的次数，可以在 O(n) 时间复杂度内解决。

func pathSum(root *TreeNode, targetSum int) int {
   
    prefix := map[int]int{
   0: 1}
    return dfs(root, 0, targetSum, prefix)
}

func dfs(node *TreeNode, currSum, target int, prefix map[int]int) int {
   
    if node == nil {
   
        return 0
    }
    currSum += node.Val
    count := prefix[currSum - target]
    prefix[currSum]++
    count += dfs(node.Left, currSum, target, prefix)
    count += dfs(node.Right, currSum, target, prefix)
    prefix[currSum]-- // 回溯
    return count
}

🔍 重点注意：

• 暴力法时间复杂度为 O(n²)，使用前缀和优化可降低为 O(n)；
• 注意回溯阶段要恢复前缀和的状态，避免影响其它路径。

2️⃣ LeetCode 236. 二叉树的最近公共祖先（LCA）

🧩 题目描述

给定一棵二叉树，找到两个节点 p 和 q 的最近公共祖先。最近公共祖先定义为：在树中最深的那个节点，既是 p 的祖先也是 q 的祖先。

🧠 思路：后序遍历递归查找

我们可以使用后序遍历思路进行查找：

• 若当前节点为 null，返回 nil；
• 若当前节点等于 p 或 q，返回当前节点；
• 分别递归左子树和右子树：
  • 若左右子树均不为空，则当前节点是最近公共祖先；
  • 若只有一边非空，则返回非空的那边。

✅ 实现代码：

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
   
    if root == nil || root == p || root == q {
   
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
   
        return root
    }
    if left != nil {
   
        return left
    }
    return right
}

🔍 重点理解：

• 核心是“自底向上”的判断思路；
• 若一个节点的左右子树分别包含 p 与 q，则该节点即为最近公共祖先；
• 若递归结果为非空，需层层向上传递。

📌 总结

这类题目在真实面试中非常常见，是对树形结构中路径与节点关系判断的集中体现，理解本质后举一反三非常重要。