二叉树的最近公共祖先：情况思考

题目

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

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

思考

这道题无非四种情况

1. 全空，没有，不必判断

2. 一空，肯定在非空那边

3. 无空，当前节点为要找的

4. 节点为p或者q，当前节点上报找祖先

代码

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

//        根节点为p或者q
        if (root == p || root == q) {
            return root;
        }

//        后续遍历
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        TreeNode left = lowestCommonAncestor(root.left, p, q);

//        找到两个
        if (right != null && left != null) {
            return root;
        }

        //        找到一个
//        注释这段和下面的三目运算符一样的作用
//        if (right != null && left == null) {
//            return root.right;
//        } else if(right == null && left != null) {
//            return root.left;
//        }
        return (left != null) ? left : right;
    }
}

‍