题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
例：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
方法：递归
想要寻找公共祖先，最好的方式就是自底向上的查找，为了实现该查找方式，应该使用后序遍历
- 判断节点是否为空，或节点为p，或节点为q，若是，则返回该节点
※ 遇到节点 p（或 q）直接返回的原因： 最近公共祖先一定不在 p 的子树中。若在之后的遍历中并未遇到 q，那么表示 q 在 p 的子树中，所以 p 为最近公共节点。若在之后的遍历中遇到 q，表示 p 在 q 的子树中，或 p 和 q 存在于某个节点的左右两个子树中 - left 存放节点的左子树的返回值，right 存放节点的右子树的返回值
- 若节点的左右子树的返回值 left 和 right 均不为空，表示此时的节点即为最近公共祖先，返回该节点；若节点的左子树的返回值 left 不为空，但是右子树的返回值 right 为空，表示该节点并非最近公共公共祖先，返回左子树的返回值 left；若节点的右子树的返回值 right 不为空，但是左子树的返回值 left 为空，表示该节点并非最近公共祖先，返回右子树的返回值 right（若节点的左右子树均为空，那么无论返回 left 还是 right 均相同，即返回空）
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
if not root or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
if left:
return left
return right
例：
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
lowestCommonAncestor(3, 5, 1)：
left = lowestCommonAncestor(5, 5, 1)：因为 root == p，返回 root，即返回 5
right = lowestCommonAncestor(1, 5, 1)：因为 root == q，返回 root，即返回 1
因为 left 和 right 均存在，即表示该节点为最近公共祖先，返回 root，即返回 3
