Description:
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
Example:
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Link:
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/#/description
解题方法：
看到一种很巧妙的递归的解题方法：
1、从一个节点的左右子树本别去找p和q。
2、如果某个节点正是p和q其中一个，则返回本节点。
3、当在一个节点的左右子树找全了p和q，则返回本节点；如果没找全，则返回找到的那边；如果都没找到，则返回NULL。
可行性分析：
针对这种解题方法，容易产生一个地方的疑问：
当这个节点是p和q中的一个，并且这个节点的左右子树包含p和q中另一个怎么办？
其实这种递归方法的返回值来源只有这么几个：1某个符合条件的节点自身，2p节点，3q节点，4NULL。
下面分析一下这几个来源：
1）在节点左右都没找到的情况下
2）在本节点本身为NULL的情况下才有。
p和q节点来源于二叉树里面p和q节点本身。
当在递归函数中，先检查自身是不是p或q，意味着先从根的方向检查，如果这个节点是p和q其中一个，则这个节点变成了以上来源2或者3。如果这个节点的子树包含p和q中另一个，那么其他所有节点都不会成为以上的来源1。这意味着最后到root节点那一层这个节点会被保留下来。
如p和q不是以以上形式存在二叉树，而是有一个共同祖先的话。那么以上的来源2最终会在某个节点形成来源1。并且其他以外的节点都不会成为符合以上123来源的任何一个，只会是NULL。所以成为来源1的节点最终会被root那一层选择为返回节点。
Tips:
递归方法第三步的判断（即左右有一个则返回一个，没有则返回NULL）可以写在一起。
完整代码：
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
if(!root || !p || !q)
return NULL;
if(root == p || root == q) //如果本节点就是p或q，则返回本节点
return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(left && right) //如果p和q都在本节点的左右子树中找到，则返回本节点
return root;
return left ? left : right; //左右找到一个就返回找到的那个，否则返回NULL
}
