路径和与最近公共祖先
通过递归深入遍历普通二叉树，解决根到叶路径和、所有路径和及最近公共祖先问题。
路径和与最近公共祖先 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
根到叶路径总和
路径总和问题要判断是否存在某条根到叶路径，使其节点值之和等于目标值。将剩余目标值传入递归，并减去每个节点的值。在叶节点处，检查剩余值是否等于该叶节点的值。这样无需维护显式的路径列表，同时节省空间且代码简洁。边界情况：空树没有路径，因此请立即返回 False。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def has_path_sum(root, target):
if not root:
return False
if not root.left and not root.right: # leaf
return root.val == target
remain = target - root.val
return (has_path_sum(root.left, remain) or
has_path_sum(root.right, remain))
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22)) # True: 5->4->11->2所有根到叶路径
要枚举所有路径，请维护一个不断累积的路径列表。在每次递归调用中，先追加当前节点的值，递归处理子节点，然后在返回时执行弹出操作（回溯）。到达叶节点时，记录当前路径的快照（list(path)）。这种“选择、递归、取消选择”的模式是树结构回溯的基础。
def all_path_sums(root, target):
results = []
def dfs(node, path, remaining):
if not node:
return
path.append(node.val)
if not node.left and not node.right and remaining == node.val:
results.append(list(path)) # snapshot
else:
dfs(node.left, path, remaining - node.val)
dfs(node.right, path, remaining - node.val)
path.pop() # backtrack
dfs(root, [], target)
return results
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.right = TreeNode(2)
root.right.right = TreeNode(5)
print(all_path_sums(root, 22)) # [[5,4,11,2]]路径总和 III：任意路径、任意节点
路径总和 III（LeetCode #437）统计总和等于目标值的路径，其中路径可以从任意位置开始并在任意位置结束（不局限于根到叶）。暴力方法的时间复杂度为 O(n²)：从每个节点执行一次 DFS。最优的 O(n) 方法使用前缀总和哈希表：跟踪不断累积的总和，并统计 current_sum - target 之前出现过的次数，这与子数组总和问题的方法相似。
def path_sum_iii(root, target):
prefix_counts = {0: 1}
def dfs(node, running_sum):
if not node:
return 0
running_sum += node.val
count = prefix_counts.get(running_sum - target, 0)
prefix_counts[running_sum] = prefix_counts.get(running_sum, 0) + 1
count += dfs(node.left, running_sum)
count += dfs(node.right, running_sum)
prefix_counts[running_sum] -= 1 # backtrack
return count
return dfs(root, 0)
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(-3)
root.left.left = TreeNode(3)
root.left.right = TreeNode(2)
root.right.right = TreeNode(11)
root.left.left.left = TreeNode(3)
root.left.left.right = TreeNode(-2)
root.left.right.right = TreeNode(1)
print(path_sum_iii(root, 8)) # 3什么是最低公共祖先？
二叉树中两个节点 p 和 q 的最低公共祖先（LCA），是同时拥有 p 和 q 作为后代的最深节点（节点可以是自身的后代）。LCA 会出现在“两个节点之间的距离”“两个节点之间的路径”和 BST 范围查询等问题中。理解 LCA 是解决中等难度树问题的必备基础。
# 3
# / \
# 5 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
# LCA(5, 1) = 3 (root)
# LCA(5, 4) = 5 (p itself is ancestor of q)
# LCA(6, 4) = 5
# LCA(7, 4) = 2
# Key insight: the LCA is the node where p and q
# first 'split' into different subtrees.
print('LCA: deepest node that is ancestor of both p and q')LCA 递归算法
优雅的递归 LCA 解法会返回第一个满足以下条件的节点：它是 p 或 q，或者其子树中同时包含二者。如果当前节点是 p 或 q，则返回该节点。否则递归处理左子树和右子树。如果两侧都返回非空结果，则当前节点就是 LCA。如果只有一侧非空，则将该结果向上返回。该算法的时间复杂度为 O(n)，空间复杂度为 O(h)。
def lowest_common_ancestor(root, p, q):
# Base case: empty or found one of the targets
if not root or root == p or root == q:
return root
# Search both subtrees
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
# If both sides found something, this node is the LCA
if left and right:
return root
# Otherwise, return whichever side found something
return left if left else right
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
p, q = root.left, root.right # 5 and 1
lca = lowest_common_ancestor(root, p, q)
print(lca.val) # 3节点可以是自身祖先时的 LCA
一个关键的边界情况是：如果 p 是 q 的祖先（或反过来），那么 LCA 就是 p 本身。递归算法会自动处理这种情况——到达 p 时立即返回 p，不会继续查看 p 的子树。父节点会发现一侧返回了 p，另一侧返回了空值，于是将 p 作为 LCA 向上返回。编写 LCA 时，请始终通过测试验证这种情况。
# Test case: p is ancestor of q
# Tree: 3 -> left=5 -> left=6
# LCA(5, 6) should be 5
root = TreeNode(3)
root.left = TreeNode(5)
root.left.left = TreeNode(6)
p = root.left # node 5
q = root.left.left # node 6
lca = lowest_common_ancestor(root, p, q)
print(lca.val) # 5 (p itself is the LCA)带父指针的 LCA
如果每个节点都有父指针，LCA 问题就可以转化为“两个链表的相交”问题。先将 p 的祖先收集到一个集合中，然后从 q 开始向上遍历，直到找到集合中的节点。这种时间复杂度为 O(h)、空间复杂度为 O(h) 的方法很常见于系统设计面试：在这类面试中，您可以控制节点结构并存储父节点引用。
class NodeWithParent:
def __init__(self, val, parent=None):
self.val = val
self.parent = parent
self.left = None
self.right = None
def lca_with_parent(p, q):
ancestors = set()
# Collect all ancestors of p
node = p
while node:
ancestors.add(node)
node = node.parent
# Walk up from q until we hit a known ancestor
node = q
while node:
if node in ancestors:
return node
node = node.parent
return None
print('With parent pointers: O(h) time and space')二叉搜索树中的 LCA
在 BST 中，LCA 更简单，因为排序性质可以告诉您每个节点位于哪个子树中。如果 p 和 q 都小于当前节点，LCA 就在左子树中。如果二者都大于当前节点，LCA 就在右子树中。否则，当前节点将二者分隔开，因此它就是 LCA。对于平衡 BST，这会将问题的时间复杂度降至 O(log n)。
def lca_bst(root, p, q):
if not root:
return None
if p.val < root.val and q.val < root.val:
return lca_bst(root.left, p, q) # both in left
if p.val > root.val and q.val > root.val:
return lca_bst(root.right, p, q) # both in right
return root # split point = LCA
# Iterative BST LCA (no recursion overhead):
def lca_bst_iter(root, p, q):
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return root
return None
print('BST LCA: O(log n) for balanced trees')两个节点之间的距离
树中两个节点之间的距离等于连接它们的路径上的边数。可以直接根据 LCA 计算：distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q))。请先找到 LCA，再计算每个节点的深度。使用恰当的辅助函数时，时间复杂度为 O(n)，空间复杂度为 O(h)。
def find_depth(root, target, depth=0):
if not root:
return -1
if root == target:
return depth
left = find_depth(root.left, target, depth + 1)
if left != -1:
return left
return find_depth(root.right, target, depth + 1)
def node_distance(root, p, q):
lca = lowest_common_ancestor(root, p, q)
# depth from LCA to p and q
dp = find_depth(lca, p)
dq = find_depth(lca, q)
return dp + dq
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(node_distance(root, root.left.left, root.left.right)) # 2最大根到叶路径和
最大根到叶路径和会跟踪从根节点到当前节点的累积总和。到达叶节点时，将其与全局最大值进行比较。这是一种前序 DFS，当前路径总和作为参数传递。与通用的最大路径和不同，此版本只考虑根到叶路径，因此更简单——无需考虑任意节点之间的路径。
def max_root_to_leaf_sum(root):
if not root:
return float('-inf')
best = [float('-inf')]
def dfs(node, running):
running += node.val
if not node.left and not node.right: # leaf
best[0] = max(best[0], running)
return
if node.left:
dfs(node.left, running)
if node.right:
dfs(node.right, running)
dfs(root, 0)
return best[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(max_root_to_leaf_sum(root)) # 1+2+5 = 8根到叶数字之和
根到叶数字之和（LeetCode #129）将每条根到叶路径视为一个十进制数字（例如，路径 1→2→3 表示数字 123），并要求计算这些数字的总和。通过递归传递 current_number * 10 + node.val 来构造数字。在每个叶节点处，将完整的数字加到总和中。这是一个简洁的示例，展示了如何通过前序 DFS 向下传递累积状态。
def sum_numbers(root):
def dfs(node, num):
if not node:
return 0
num = num * 10 + node.val
if not node.left and not node.right: # leaf
return num
return dfs(node.left, num) + dfs(node.right, num)
return dfs(root, 0)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(sum_numbers(root)) # 12 + 13 = 25
root2 = TreeNode(4)
root2.left = TreeNode(9)
root2.right = TreeNode(0)
root2.left.left = TreeNode(5)
root2.left.right = TreeNode(1)
print(sum_numbers(root2)) # 495 + 491 + 40 = 1026快速检查
请测试您对本课数据结构与算法——编程面试准备相关概念的理解。
课程回顾
在本课中，您学习了：路径总和的不同变体（根到叶、所有路径、使用前缀总和的路径总和 III），使用优雅的递归分割求最低公共祖先，以及利用排序性质在 O(log n) 时间内求BST 的 LCA。接下来我们将开始学习二叉搜索树，包括插入和搜索操作。
常见问题解答
「路径和与最近公共祖先」课时是免费的吗？
是的 — 「路径和与最近公共祖先」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「路径和与最近公共祖先」这节课中我会学到什么？
通过递归深入遍历普通二叉树，解决根到叶路径和、所有路径和及最近公共祖先问题。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「路径和与最近公共祖先」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- TreeNode 类与层序 BFS
- 中序、前序、后序 DFS
- 直径、高度与平衡树
- 路径和与最近公共祖先