leetcode hot 100二叉树最近公共祖先

本题要找二叉树的最近公共祖先，会出现两种情况，
第一种比如p=7，q=4，这时候，2就是最近公共祖先
第二种比如p=7，q=2，这时候，2也是公共祖先。
两种情况不同的是，p与q的层级关系，
我们只需要找到p或者q，直接向上一层返回结果就可以了。
那么我们这个题，需要先知道左节点是不是有p或者q，有的话就往上返回，再同样判断右节点有没有p或者q。再处理中间节点，即返回的值。所以我们需要采用后序遍历，即左中右。

依旧采用递归，确定递归函数的参数以及返回值（我们需要返回最近公共祖先节点，然后传入root，p，q）。

然后确定结束条件（当root==Null的时候，直接返回null。当当前节点是p或者是q的时候，直接返回当前节点）注意，当前节点我们传入的是root，不一定代表根节点。

然后确定单层递归处理逻辑：因为采用后序，所以是左右中。首先递归左节点，然后递归右节点。最后的时候处理返回的节点（中）。

这时候可能会出现几种情况，比如节点的左节点是空，右节点也是空，那么说明不存在公共祖先，返回空；如果左不为空，右为空或者左为空，右不为空，这时候分别返回左节点、右节点即可；如果左右都不为空，说明当前节点是公共祖先，直接返回当前节点即可。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) { // 递归结束条件
            return root;
        }

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

        if(left == null && right == null) { // 若未找到节点 p 或 q
            return null;
        }else if(left == null && right != null) { // 若找到一个节点
            return right;
        }else if(left != null && right == null) { // 若找到一个节点
            return left;
        }else { // 若找到两个节点
            return root;
        }
    }
}