二叉搜索树的最近公共祖先

发表于
本文字数： 2k 阅读时长 ≈ 2 分钟

LeetCode每日一题，538. Convert BST to Greater Tree

先看题目描述

大意就是给定一棵二叉搜索树和两个节点，返回这两个节点的最低公共祖先，并且自己也算自己的祖先

算法和思路

这题挺简单，利用二叉搜索树的性质就可以，即根节点的左子树上节点都比根节点小，右子树上节点都比根节点大

  • 我们从根节点开始遍历；

  • 如果当前节点的值大于 p 和 q 的值，说明 p和 q 应该在当前节点的左子树，因此将当前节点移动到它的左子节点；

  • 如果当前节点的值小于 p 和 q 的值，说明 p 和 q 应该在当前节点的右子树，因此将当前节点移动到它的右子节点；

  • 如果当前节点的值不满足上述两条要求，那么说明当前节点就是「分岔点」。此时，p 和 q 要么在当前节点的不同的子树中，要么其中一个就是当前节点

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (isSubnode(p, q)) return p;
        if (isSubnode(q, p)) return q;
        if (p.val < q.val) return search(root, p ,q);
        else return search(root, q ,p);

    }

    private boolean isSubnode(TreeNode root, TreeNode sub) {
        if (root == null) return false;
        if (root.val == sub.val) return true;
        if (root.val < sub.val) return isSubnode(root.right, sub);
        else return isSubnode(root.left, sub);
    }

    private TreeNode search(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val < root.val && q.val > root.val) return root;
        else if (p.val < root.val && q.val < root.val) return search(root.left, p, q);
        else return search(root.right, p, q);
    }
}

下面是题解给的代码，和我上面这个自己实现的运行效率相同，但代码更优美，更简洁明了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while (true) {
            if (p.val < ancestor.val && q.val < ancestor.val) {
                ancestor = ancestor.left;
            } else if (p.val > ancestor.val && q.val > ancestor.val) {
                ancestor = ancestor.right;
            } else {
                break;
            }
        }
        return ancestor;
    }
}