leetcode: Lowest Common Ancestor of a Binary Search Tree

问题描述

 Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

原问题链接：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/ 

 

问题分析

    这个问题相对很简单，只要知道二叉搜索树的都知道，它的一个基本特性就是 任何一个节点，它比自己的左子树值大，同时比自己的右子树小。所以如果要给定树上面两个节点，并查找它最低公共父节点的话，可以这样来考虑：

    首先考虑最低公共父节点，既然是最低的公共父节点，必然这个节点是如下几种情况，

1. 存在一个节点，给给定的两个节点分别在它的左右子树中。这种情况最常见，如下图：

 

    在该图中，我们选择的节点是6和9，它们最低公共父节点是8.

2. 一个节点是另外一个节点的父节点，这种情况我们也可以称那个处于父节点位置的节点为它们的最低公共父节点，如下图：

 

    在该图中，5节点是6节点的父节点，它也就是它们的最低公共父节点。

    既然我们要找的是两个节点的最低公共父节点，所以它们都有一个比较有意思的特征，就是该最低公共父节点一定满足 m.val >= p.val && m.val <= q.val，假设p, q表示我们给定的两个节点。为什么不是m节点的父节点呢？因为m节点必然是它父节点的左子节点或者右子节点。这样它的父节点相对节点p, q就不满足上述的关系了。

 

    既然定义好了这个特性我们就来进一步分析怎么来查找这个节点。我们首先能够访问的节点是根节点root。对于该节点来说，如果p, q两个节点的值都小于它的值，则说明这两个节点在它的左子树，我们可以到它的左子树做进一步的查找。如果p, q两个节点的值都大于它的值，则说明应该去它的右子树查找。而对于其他的情况则说明我们找到了符合条件的节点。这样我们可以得到如下的代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
        return root;
    }
}

    非常简单，没什么好说的。当然，我们也可以写一个非递归版的实现：

 

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(true) {
            if(root.val > p.val && root.val > q.val) root = root.left;
            else if(root.val < p.val && root.val < q.val) root = root.right;
            else return root;
        }
    }
}

 

总结

    这个问题总的来说还是比较好找思路。重点在于它的最低父节点满足m.val > p.val && m.val < q.val。而且它们互为充分必要条件。所以我们要找这个节点的时候只需要根据当前节点和两个节点的值比较去选择下一步去哪个子树就可以了。当然，从这个问题衍生出来的问题还有更复杂的，比如针对普通二叉树的情况，它不是二叉搜索树，那么这种情况该怎么处理呢？我们在后面的文章中继续讨论。