236. 二叉树的最近公共祖先

236. 二叉树的最近公共祖先

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

注意 : 一个节点也可以是它自己的祖先

提示：
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

题目解析：一个节点可以是自己的祖先，p和q一定是两个不同的节点 没有相等的可能

思路：递归遍历二叉树
在以root为根节点的二叉树中查找p q的最近公共祖先
会有4种情况：

1. 如果p q同时存在于这棵二叉树中，就能成功返回它们的最近公共祖先
2. 如果p q都不存在于这棵二叉树中，就返回null
3. 如果只有p存在于这棵二叉树中，就返回p
4. 如果只有q存在于这棵二叉树中，就返回q
   时间复杂度: O(n) 二叉树的所有节点有且只会被访问一次，因此时间复杂度为O(n)
   空间复杂度: O(n) 递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链

时间复杂度: O(n)
空间复杂度:O(1)
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        //特殊情况处理  根节点为空 或 p q 两个中的任意一个等于根节点 那么就返回root
        if(root == null || p == root ||q == root) return root;
         //以root.left为根节点 查找p、q的最近公共祖先
         TreeNode left = lowestCommonAncestor(root.left,p,q);
         //以root.rigth为跟节点 查找p、q的最近公共祖先
         TreeNode right = lowestCommonAncestor(root.right,p,q);
         
         //1. 左边右边各返回一个节点说明p、q分别在左右两侧，这时最近根节点就是root
         if(left != null && right != null) return  root;

        //2.left != null && right == null 左边找到最近公共祖先 返回 left
        //3.left == null && right == null 左右都没找到 返回 null 但right==null 所以返回right
        //4.left == null && right != null 右侧找到最近公共祖先 返回right
        //整合后可以用三目运算来表示
        return (left != null)?left:right;
         
    }
}

执行结果.png