题目描述(简单难度)

从二叉搜索树中,找出两个节点的最近的共同祖先。

二叉搜索树定义如下。

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的节点。

解法一 递归

由于是二叉搜索树,所以找最近的共同祖先比较容易,总共就三种情况。

  • 如果给定的两个节点的值都小于根节点的值,那么最近的共同祖先一定在左子树
  • 如果给定的两个节点的值都大于根节点的值,那么最近的共同祖先一定在右子树
  • 如果一个大于等于、一个小于等于根节点的值,那么当前根节点就是最近的共同祖先了

至于前两种情况用递归继续去解决即可。

代码的话,我们可以通过交换使得 p.val <= q.val ,这样就可以简化后边 if 语句的判断。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

    // 保持 p.val <= q.val
    if (p.val > q.val) {
        return lowestCommonAncestor(root, q, p);
    }
    //如果有一个是根节点就可以提前结束, 当然这个 if 不要也可以
    if (p.val == root.val || q.val == root.val) {
        return root;
    }
    if (q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    } else if (p.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    } else {
        return root;
    }

}

解法二 迭代

上边的递归比较简单,可以直接改写成循环的形式。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    int pVal = p.val;
    int qVal = q.val;
    if (pVal == root.val || qVal == root.val) {
        return root;
    }
    // 保持 p.val <= q.val
    if (pVal > qVal) {
        int temp = pVal;
        pVal = qVal;
        qVal = temp;
    }
    while (true) {
        if (qVal < root.val) {
            root = root.left;
        } else if (pVal > root.val) {
            root = root.right;
        } else {
            return root;
        }
    }
}

只要知道二叉搜索树的定义,这个题就很好解了。当然之前的题目都是用的二叉搜索树的另一个性质,「中序遍历输出的是一个升序数组」,比如刚做完的 230 题

对于二叉树的题,开始可以用递归的思想去思考会比较简单。

results matching ""

    No results matching ""