235. 二叉搜索树的最近公共祖先（BST）

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

• 题目
• 解题思路
• 代码

题目

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

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

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

说明:

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉搜索树中。

解题思路

树的问题二话不说先把递归结构写好。然后分析情况。
    这题有三个大情况：
        ①p,q都在以root为根的树中，返回p,q的最近公共祖先
        ②p,q都不在以root为根的树中，返回null
        ③p,q只有一个在以root为根的树中，返回在树中的那个节点

        把情况①（p,q都在以root为根的树中）拎出来看一下细节情况：
            ①p,q中有一个就是root，比如p==root，则直接返回root，当然，依据情况③，只要p或者q有一个和root相等，就返回哪一个。
            ②p,q都不等于root，那么对于p,q的公共祖先T来说，T的left肯定就是p，T的right就是q

代码

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //base case
        if(root==null){
            return null;
        }

        if(root==p||root==q){//如果root是p或者q其中一个，那root就是他们的公共祖先
            return root;
        }

        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        //上面的base case保证了到达这里的root不为空，也不为p或者q
        //情况一：p,q都在以root为根的节点中，因为用的是后序遍历，所以对于p、q的公共祖先来说p一定是它的left，q一定是它的right
        if(left!=null&&right!=null){
            return root;
        }
        //情况二：俩都为null，即root没有子树，p,q都不在以root为根节点的树中
        if(left==null&&right==null){
            return null;
        }

        //情况三：只有p或者q在以root为根节点的树中，那就只返回该节点
        return left==null?right:left;

        

    }
}