19 | 面试题：二叉树&二叉搜索树的最近公共祖先-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

### 19 | 面试题：二叉树&二叉搜索树的最近公共祖先

在面试中，关于二叉树及其变体（如二叉搜索树）的问题频繁出现，其中一个经典而富有挑战性的问题便是求解两个节点的最近公共祖先（Lowest Common Ancestor, LCA）。这个问题不仅考察了应聘者对树结构特性的理解，还考验了其递归思维和算法设计能力。本章节将详细探讨在普通二叉树和二叉搜索树中求解LCA的不同方法。

#### 一、引言

在树结构中，最近公共祖先是指两个节点在树中深度最大的共同祖先。对于二叉树而言，由于每个节点最多有两个子节点（左子节点和右子节点），这个问题变得既具体又富有挑战性。根据树的不同类型（普通二叉树与二叉搜索树），求解LCA的策略也会有所不同。

#### 二、普通二叉树中的LCA求解

在普通二叉树中，没有额外的性质（如二叉搜索树的排序性质）可以利用，因此求解LCA通常依赖于递归或迭代遍历树，同时记录访问过的节点信息。

##### 2.1 递归方法

递归是解决此类问题最直观的方法之一。基本思路是，对于当前节点`node`，如果它等于`p`或`q`中的一个，则直接返回该节点（可能是LCA）。否则，递归地在左子树和右子树中分别寻找`p`和`q`，并根据以下情况处理：

1. 如果左子树返回了`p`或`q`的任一节点，且右子树也返回了另一个节点或LCA，则当前节点就是LCA。
2. 如果左子树和右子树都返回了`null`，说明`p`和`q`都不在当前子树中，返回`null`。
3. 如果只有一个子树返回了非`null`值（即`p`或`q`中的一个），则返回该值。

```java
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) {
        return root; // 左右子树分别找到了p和q
    }
    return left != null ? left : right; // 只在一边找到了
}
```

##### 2.2 哈希表+遍历（非递归）

另一种思路是首先使用哈希表记录从根到目标节点`p`和`q`的路径，然后比较这两条路径找到第一个共同的节点。这种方法的空间复杂度较高，但在某些特定场景下（如树较深但节点数不多时）可能更有效率。

#### 三、二叉搜索树中的LCA求解

在二叉搜索树（BST）中，由于每个节点的左子树只包含小于该节点的元素，右子树只包含大于该节点的元素，这一性质为求解LCA提供了额外的便利。

##### 3.1 利用BST性质

对于BST中的两个节点`p`和`q`，我们可以利用它们的值来推断它们与根节点的相对位置关系，从而更有效地找到LCA。

1. **初始化**：从根节点开始。
2. **比较与移动**：
   - 如果`p`和`q`的值都小于当前节点的值，则LCA一定在当前节点的左子树中，递归向左子树查找。
   - 如果`p`和`q`的值都大于当前节点的值，则LCA一定在当前节点的右子树中，递归向右子树查找。
   - 如果上述两种情况都不满足（即`p`和`q`分别在根节点的两侧），则当前节点即为LCA。

```java
public TreeNode lowestCommonAncestorBST(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {
        return root;
    }
    // p和q的值都小于根节点的值，则LCA在左子树
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestorBST(root.left, p, q);
    }
    // p和q的值都大于根节点的值，则LCA在右子树
    if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestorBST(root.right, p, q);
    }
    // p和q分别在根节点的两侧，则根节点即为LCA
    return root;
}
```

#### 四、优化与讨论

- **空间复杂度**：递归方法的空间复杂度主要取决于递归栈的深度，最坏情况下为O(n)（当树退化为链表时）。对于BST，由于我们总是能更快地定位到目标节点的方向，所以递归深度通常会小于普通二叉树。
- **时间复杂度**：在平均情况下，对于平衡的二叉树（包括BST），时间复杂度为O(log n)（n为节点数），因为每次递归都使搜索范围减半。但在最坏情况下（树退化为链表），时间复杂度为O(n)。
- **实际应用**：在数据库索引、文件系统、版本控制系统中，LCA的概念有着广泛的应用。了解并掌握在二叉树及其变体中求解LCA的方法，对于解决这些领域的实际问题至关重要。

#### 五、总结

本章节详细探讨了在普通二叉树和二叉搜索树中求解两个节点的最近公共祖先（LCA）的方法。通过递归和BST特有性质的应用，我们展示了如何在不同类型的树结构中高效地找到LCA。这些方法不仅对于面试准备至关重要，也是理解树结构特性和算法设计能力的重要体现。希望读者能够通过本章节的学习，加深对树结构和LCA问题的理解，并在未来的编程实践中灵活运用这些知识。

该分类下的相关小册推荐：

数据结构与算法(上)

业务开发实用算法精讲

数据结构与算法(中)

数据结构与算法(下)

编程之道-算法面试(下)

数据结构与算法之美

编程之道-算法面试(上)