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

题目描述

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

解题思路

首先明确二叉搜索树的概念

• 根节点的值大于等于左孩子节点的值
• 根节点的值小于等于右孩子节点的值
• 根节点的左子树和右子树也是二叉搜索树

假设两个指定节点分别为p、q，且p < q，由上可得，对于二叉搜索树的一个节点t，会有如下三种情况：

• 若p < root 且 q < root，则两个节点的最近公共祖先在root的左子树中。
• 若p > root 且 q > root，则两个节点的最近公共祖先在root的右子树中。
• 若p <= root且 q >= root，则两个节点的最近公共祖先为root。

Code

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //交换p、q值
        if(p.val > q.val){
            return lowestCommonAncestor(root,q,p);
        }
        if(p.val <= root.val && q.val >= root.val){
            return root;
        }
        TreeNode ans = new TreeNode();
        if(p.val < root.val && q.val < root.val){
            ans = lowestCommonAncestor(root.left,p,q);
        }else if(p.val > root.val && q.val > root.val){
            ans = lowestCommonAncestor(root.right,p,q);
        }
        return ans;
    }
}