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

题目链接：

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

解题思路：

递归看起来是从上往下，实际上从下往上的。如果发现在左右子树一个为空，一个不为空，就证明在那个不为空的子树。我们不需要关心p和q到底返回的是具体哪个，只需要知道左右不为空就行

有三种情况，p q 都在左子树或右子树，p q分别在左子树和右子树，

判断当前遍历的节点是否为空，为空返回null，节点是否等于p，是否等于q，是的话返回null。

之后判断left 和right是否为空，若都不为空，则当前root为答案，若其中一个为空，则返回另一边，为答案。

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 class Solution {
11     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
12         if(root==null || root==p||root==q)
13             return root;
14         TreeNode left = lowestCommonAncestor(root.left,p,q);
15         TreeNode right = lowestCommonAncestor(root.right,p,q);
16         if(left!=null && right!=null)
17             return root;
18         if(left==null)
19             return right;
20         return left;
21     }
22 }