题目：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
提示：
- 所有
Node.val互不相同。 p != q
思路：
利用后序遍历，设置两个flag，初始值都为false，每个遍历的节点都判断两个flag是否都为true，若是则返回该节点；否则判断是否为p或q，若为p或q则设置对应的flag为true，否则继续遍历整棵树。
class Solution {
public:
TreeNode* parent;
TreeNode* LowestCommonAncestorAux(TreeNode* root, TreeNode* p, TreeNode* q)
{
if(NULL == root) return NULL;
TreeNode* left_node = NULL, *right_node = NULL;
left_node = LowestCommonAncestorAux(root->left, p, q);
right_node = LowestCommonAncestorAux(root->right, p, q);
if(NULL != left_node && NULL != right_node)
{
parent = root;
return root;
}
if(root->val == p->val || root->val == q->val)
{
if(NULL != left_node || NULL != right_node)
{
parent = root;
return root;
}
return root;
}
if(left_node) return left_node;
if(right_node) return right_node;
return NULL;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
LowestCommonAncestorAux(root, p, q);
return parent;
}
};
思路有一点问题，上述代码是看过代码随想录的思路做出来的。使用flag是有问题的，因为只知道已经遍历过两个目标节点了，其余的一概不知。
如：第二个flag为true时，我们需要判断上个节点是否为该节点的子孙节点。若不是，还需要继续遍历，遍历到新的节点后，判断该新节点的左右孩子是否为目标节点，必须遍历，因为不知道节点的位置。。。
使用代码随想录的思路，当遍历到某个节点时，便返回该节点。并在每次递归中都判断，左右孩子是否有返回值，这样就能找到最近的祖先节点。
版本2：
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == q || root == p || root == NULL) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != NULL && right != NULL) return root;
if (left == NULL) return right;
return left;
}
};