【leetcode-235】二叉搜索樹的最近公共祖先
2022-05-11 10:58:31

??235. 二叉搜索樹的最近公共祖先??

題目:

思路:

看到二叉樹的題目,首先要想到遞歸,因為大多數的二叉樹題目都是可以通過遞歸來解決的,再看這是一個二叉搜索樹,立馬就想到二叉搜索樹的特質,左子樹上所有節點的值都小于根節點的值,右子樹上所有節點的值都大于根節點的值,它的左右子樹也分別為二叉搜索樹.那我們怎么能利用這個性質呢?

可以分三種情況來分析問題:

1. p,q 都比 root 節點值小,所以 p,q 都在左子樹.
2. p,q 都比 root 節點值大,所以 p,q 都在右子樹.
3. p,q 一個比 root 節點值小,一個比 root 節點值大,也就是 p,q 分布在 root 節點的左右子樹兩邊.或者 p,q 其中一個節點就是 root 節點,此時都應該直接返回 root.

代碼:

分析完所有的情況后,代碼就比較好寫了.根據上面的思路,解題代碼如下所示:

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

提交結果: