本文共 2093 字，大约阅读时间需要 6 分钟。

Binary Search Tree的最低公共祖先问题

随着对数据结构的深入学习，我最近关注了一个经典的二叉搜索树问题：二叉搜索树中的最低公共祖先（Lowest Common Ancestor，LCA）。这个问题看似简单，但却对理解二叉搜索树的结构和遍历方法有很深的帮助。

问题描写

最低公共祖先的定义是以二叉搜索树为前提，找出给定两个节点的最近的共同祖先节点。这类似于我们在家庭树中找某两个人的最低共同祖先。假设给定两个节点，它们都在左边或者右边的子树中，那么这个共同的祖先节点就是它们的最近的共同点。

思路及代码

对于二叉搜索树，我们可以利用其具有的有序性来解决这个问题。二叉搜索树有一个重要性质：左子树中的所有节点的值都小于根节点的值，右子树的值都大于根节点的值。基于这个性质，我们可以使用一种递归的方法来比较两个节点的位置关系。

具体来说，我们从根节点开始：

基于上述逻辑，我们可以编写一个递归函数来查找最低公共祖先。以下是实现代码：

public class Solution {    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {        if (root == null) {            return null;        }        // 比较当前节点的值与p和q的值        boolean pInLeftSubtree = root.val > p.val;        boolean qInLeftSubtree = root.val > q.val;        // 确定p和q的位置        if (pInLeftSubtree != qInLeftSubtree) {            // p和q不在同一个子树中，直接返回根节点作为LCA            return root;        } else if (pInLeftSubtree) {            // 两个节点都在左子树中，继续递归左子树            return lowestCommonAncestor(root.left, p, q);        } else {            // 两个节点都在右子树中，继续递归右子树            return lowestCommonAncestor(root.right, p, q);        }    }}

这个代码的逻辑非常简单，充分利用了二叉搜索树的性质，从而高效地找到两个节点的最低公共祖先。

普通二叉树的最低公共祖先问题

对于普通二叉树的问题，我们不能依赖二叉搜索树的有序性，因此需要采用一种更通用的方法。这时，我们需要用深度优先搜索（DFS）来遍历树，记录两个节点的路径，并找到它们的交点。

具体算法步骤如下：

以下是实现代码：

public class Solution {    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;        } else {            return (left != null) ? left : right;        }    }}

这个实现采用了并行的方式查找两个节点的路径，从而找到它们的交点。这种方法适用于普通二叉树，但由于采用递归方式，可能会有较大的递归深度限制。

总结

通过上述方法，我们可以轻松地解决二叉搜索树和普通二叉树的最低公共祖先问题。这些方法分别充分利用了二叉搜索树的有序性和普通二叉树的遍历特性，适用于不同的场景。

转载地址：http://yqgyk.baihongyu.com/