BST的最近公共祖先

Sep 08, 2020
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // if (!root) return nullptr;

        auto rval = root->val;
        auto pval = p->val;
        auto qval = q->val;

		// 如果p q 都比root大,那么公共祖先在右子树 返回子问题结果
        if (pval > rval && qval > rval)
            return lowestCommonAncestor(root->right, p, q);
        // 同理
        if (pval < rval && qval < rval)
            return lowestCommonAncestor(root->left, p, q);
		// 如果p q在root两边,root就是公共祖先
        return root;
    }
};
Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.