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

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

題目:

思路:

看到二叉樹的題目,首先要想到遞歸,因?yàn)榇蠖鄶?shù)的二叉樹題目都是可以通過遞歸來解決的,再看這是一個(gè)二叉搜索樹,立馬就想到二叉搜索樹的特質(zhì),左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值,右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值,它的左右子樹也分別為二叉搜索樹.那我們怎么能利用這個(gè)性質(zhì)呢?

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

1. p,q 都比 root 節(jié)點(diǎn)值小,所以 p,q 都在左子樹.
2. p,q 都比 root 節(jié)點(diǎn)值大,所以 p,q 都在右子樹.
3. p,q 一個(gè)比 root 節(jié)點(diǎn)值小,一個(gè)比 root 節(jié)點(diǎn)值大,也就是 p,q 分布在 root 節(jié)點(diǎn)的左右子樹兩邊.或者 p,q 其中一個(gè)節(jié)點(diǎn)就是 root 節(jié)點(diǎn),此時(shí)都應(yīng)該直接返回 root.

代碼:

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

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;
    }
}

提交結(jié)果: