leetcode 链接：二叉树的公共祖先
《程序员面试金典（第 6 版）》中相同题目：[中等] 4.8 首个共同祖先

题目

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例：
[中等] 236. 二叉树的最近公共祖先 - 图1

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

输入：root = [1,2], p = 1, q = 2
输出：1

解答 & 代码

解法一

想法：
如果一个节点 node 是两个节点 p、q 的最近公共祖先，那么需满足如下条件：

p 在 node 的左半边树上（p == node 或 p 是 node 的左子树节点），并且 q 在 node 的右半边树上（q == node 或 q 是 node 的右子树节点）

或者正好相反：p 在 node 的右半边树上（p == node 或 p 是 node 的右子树节点），并且 q 在 node 的左半边树上（q == node 或 q 是 node 的左子树节点）

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
  // 判定 node 节点是否是以 root 为根节点的树上的一个节点
  bool isTreeNode(TreeNode* root, TreeNode* node)
  {
      if(root == NULL)
          return false;
      if(node == NULL)
          return true;

      return root == node || isTreeNode(root->left, node) || isTreeNode(root->right, node);
  }
public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
      if(root == NULL)
          return NULL;

      bool isPLeft = (root == p) || isTreeNode(root->left, p);
      bool isPRight = (root == p) || !isPLeft;
      bool isQLeft = (root == q) || isTreeNode(root->left, q);
      bool isQRight = (root == q) || !isQLeft;

      if((isPLeft && isQRight) || (isPRight && isQLeft))
          return root;
      else if(isPLeft && isQLeft)
          return lowestCommonAncestor(root->left, p, q);
      else
          return lowestCommonAncestor(root->right, p, q);
  }
};

执行结果： ``` 执行结果：通过

执行用时：856 ms, 在所有 C++ 提交中击败了 5.48% 的用户内存消耗：13.8 MB, 在所有 C++ 提交中击败了 87.90% 的用户

<a name="mQGvI"></a>
## 解法二
后序遍历

- 时间复杂度 O(N)，N 是二叉树节点数
- 空间复杂度 O(N)，准确的说是 O(d)，d 是二叉树的深度
```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 递归结束条件1：以root为根节点的树中不含p或q，因此无共同祖先，返回NULL
        if(root == NULL)
            return NULL;
        // 递归结束条件2：以root为根节点的树中找到p或q的一个，返回该节点
        if(root == p || root == q)
            return root;

        // 递归
        // 在左子树中寻找p或q节点，只要找到其中一个就返回该节点，否则返回NULL（参考上述两个递归结束条件）
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        // 在右子树中寻找p或q节点，只要找到其中一个就返回该节点，否则返回NULL（参考上述两个递归结束条件）
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        // 如果p和q分别在不同子树中，说明root就是最近公共祖先
        if(left && right)
            return root;
        // 如果左子树中找到一个节点（p或q）而右子树中没找到，说明两个节点都在左子树中
        else if(left && !right)
            return left;
        // 如果右子树中找到一个节点（p或q）而左子树中没找到，说明两个节点都在右子树中
        else
            return right;
    }
};

执行结果：

执行结果：通过

执行用时：16 ms, 在所有 C++ 提交中击败了 89.24% 的用户
内存消耗：14 MB, 在所有 C++ 提交中击败了 33.91% 的用户