二叉树公共最近祖先

在计算机科学中，特别是在数据结构和算法领域，“最近公共祖先”（Lowest Common Ancestor，LCA）是一个在有根树或有向无环图中的概念。对于有根树 ( T ) 的两个结点 ( p ) 和 ( q )，最近公共祖先指的是树中的一个结点 ( x )，满足 ( x ) 是 ( p ) 和 ( q ) 的共同祖先，并且 ( x ) 的深度尽可能大。

在二叉树中寻找最近公共祖先的算法可以分为两种情况：

1. 二叉搜索树（Binary Search Tree, BST）

在二叉搜索树中，可以利用其特性简化查找过程：

• 如果 ( p ) 和 ( q ) 分别位于当前节点的左右两侧，则当前节点即为 LCA。
• 如果 ( p ) 和 ( q ) 都在当前节点的左侧，则在其左子树中继续查找。
• 如果 ( p ) 和 ( q ) 都在当前节点的右侧，则在其右子树中继续查找。

2. 一般二叉树

在一般的二叉树中，没有像 BST 那样的顺序关系，因此需要使用递归或者迭代的方法来遍历树并查找 LCA。

递归方法:

• 从根节点开始递归地搜索 ( p ) 和 ( q )。
• 如果当前节点等于 ( p ) 或 ( q )，则返回当前节点。
• 如果在左子树中找到了 ( p ) 或 ( q )，则返回左子树的结果。
• 如果在右子树中找到了 ( p ) 或 ( q )，则返回右子树的结果。
• 如果左子树和右子树都返回了非空结果，则说明 ( p ) 和 ( q ) 分别位于当前节点的左右两侧，所以当前节点就是 LCA。
• 如果左子树或右子树返回了空结果，而另一个子树返回了非空结果，则返回非空结果。

迭代方法:

• 使用栈来模拟递归过程，同时需要额外的空间来记录每个节点的父节点。
• 通过回溯到根节点的方式，找出 ( p ) 和 ( q ) 的路径，然后比较这两条路径找到最后一个相同的节点，这个节点就是 LCA。

在实现这类算法时，需要考虑各种边界条件，比如当 ( p ) 或 ( q ) 之一不存在于树中时如何处理等。通常情况下，算法设计时会假设 ( p ) 和 ( q ) 都存在于树中。如果需要处理这种情况，可以在遍历过程中检查是否已经找到了两个节点。

案例展示

接下来我将提供一些具体的代码实现示例，以便你更好地理解如何在二叉树中查找最近公共祖先（LCA）。我们将分别展示二叉搜索树（BST）和一般二叉树中查找LCA的Python代码实现。

二叉搜索树（BST）中查找LCA

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef lowestCommonAncestor(root, p, q):while root:if root.val > p.val and root.val > q.val: # 如果 p 和 q 都小于当前节点，向左子树移动root = root.leftelif root.val < p.val and root.val < q.val: # 如果 p 和 q 都大于当前节点，向右子树移动root = root.rightelse: # 当前节点就是 LCAreturn root

一般二叉树中查找LCA

class Solution:def lowestCommonAncestor(self, root, p, q):self.p_found = Falseself.q_found = Falseresult = self._helper(root, p, q)# 确保 p 和 q 都存在二叉树中if not self.p_found or not self.q_found:return Nonereturn resultdef _helper(self, node, p, q):if not node:return None# 检查当前节点是不是 p 或 qif node == p:self.p_found = Truereturn nodeif node == q:self.q_found = Truereturn nodeleft = self._helper(node.left, p, q)right = self._helper(node.right, p, q)# 如果 p 和 q 分别在左右子树中，那么当前节点就是 LCAif left and right:return node# 否则返回找到的节点（left 或 right）return left or right

在上述代码中，TreeNode 类用于定义二叉树的节点，而 lowestCommonAncestor 函数实现了LCA的查找逻辑。在一般二叉树的实现中，我们使用了一个辅助函数 _helper 来递归地查找 p 和 q，并使用布尔变量 p_found 和 q_found 来追踪是否已经找到了这两个节点。

希望这些代码示例能帮助你理解如何在二叉树中实现LCA的查找。如果有任何疑问或需要进一步的解释，请随时提问！

在上一部分中，我们讨论了二叉树中查找最近公共祖先（LCA）的基本算法和代码实现。现在，让我们深入探讨一些高级主题和优化技巧，以提高算法效率和代码可读性。

1. 使用哈希表存储父节点信息

在一般二叉树中，如果我们能够预先构建一个哈希表来存储每个节点的父节点信息，那么查找LCA的过程可以更加直观和高效。这种方法特别适用于需要频繁查询LCA的场景。

def build_parent_map(root, parent_map):stack = [(root, None)]while stack:node, parent = stack.pop()parent_map[node] = parentif node.left:stack.append((node.left, node))if node.right:stack.append((node.right, node))def find_path(parent_map, target, path):while target:path.append(target)target = parent_map[target]def lowestCommonAncestor(root, p, q):parent_map = {}build_parent_map(root, parent_map)path_p = []path_q = []find_path(parent_map, p, path_p)find_path(parent_map, q, path_q)i = 0while i < len(path_p) and i < len(path_q) and path_p[i] == path_q[i]:i += 1return path_p[i-1]

这段代码首先构建了一个哈希表 parent_map 来存储每个节点的父节点，然后分别找到 p 和 q 到根节点的路径，并找到这两条路径上的最后一个相同节点，即为 LCA。

2. 处理多个查询

当需要处理多个LCA查询时，预处理树的信息（如父节点、深度等）可以显著提升性能。例如，使用动态规划技术可以计算出每个节点的深度以及每个节点的(2^i)倍的祖先节点，这样在查询时可以快速跳过多个层级。

3. 异常处理

在实际应用中，应考虑各种可能的异常情况，例如：

• 如果 p 或 q 中的一个或两个不在树中，应如何处理？
• 如何处理 p 和 q 相同的情况？

在代码实现中，可以通过添加适当的边界检查来处理这些情况，确保算法的健壮性和正确性。

结论

查找二叉树中的最近公共祖先是一个经典问题，不仅在算法竞赛中常见，也是许多实际应用的基础。通过理解不同类型的二叉树和优化策略，你可以更有效地解决这一问题，并将其应用于更广泛的场景中。希望上述内容对你有所帮助！如果有任何疑问或需要进一步讨论的地方，欢迎随时提问。

😍😍 大量H5小游戏、微信小游戏、抖音小游戏源码😍😍 😍😍试玩地址： https://www.bojiogame.sg😍😍 😍看上哪一款，需要源码的csdn私信我😍

————————————————

​最后我们放松一下眼睛