给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
最近公共祖先意味着需要从下往上遍历，这就是后序遍历（左右中）的地盘了。
寻找最近祖先（以下这套逻辑包含了两种情况，情况一：p、q都为叶子节点，情况二：p、q有一个为叶子节点，另一个为根节点）：
- 入口函数：如果节点为p或者q则返回
- 中间节点逻辑处理：
- 如果left和right有返回值，则root为最近祖先
- 如果left有返回值，则将left返回
- 如果right有返回值，则将right返回
- 如果left和right为空，则返回空
代码如下：
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root==p || root==q || root==nullptr) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right) return root;
else if (left && right==nullptr) return left;
else if (right && left==nullptr) return right;
else return nullptr;
}
};