题目

设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。
注意：

这不一定是二叉搜索树
所有节点的值都是唯一的
p、q 为不同节点且均存在于给定的二叉树中

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例：

输入: 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,3,null,4], p = 4, q = 1
输出: 1

解答 & 代码

解法一

思想：p、q 的首个共同祖先 ancestor 一定满足如下条件：p、q 都在以 ancestor 为根节点的树中，且分别在左右树中（ancestor 本身同时既算左树的节点，又算右树的节点）

设置一个函数 bool isTreeNode(TreeNode* root, TreeNode* node) 用于判定 node 节点是否在以 root 为根节点的树中

寻找节点 p、q 首个共同祖先的方法：

初始 cur 指向 root 节点
如果 cur 不为 NULL ，循环：
- 如果 cur 节点就是 p，或者 p 在 cur 节点的左子树中，都算 p 在 cur 的左树中，即 pInLeft = true
- 如果 cur 节点就是 p，或者 p 在 cur 节点的右子树中，都算 p 在 cur 的右树中，即 pInRight = true
- 如果 cur 节点就是 q，或者 q 在 cur 节点的左子树中，都算 q 在 cur 的左树中，即 qInLeft = true
- 如果 cur 节点就是 q，或者 q 在 cur 节点的右子树中，都算 q 在 cur 的右树中，即 qInRight = true
- 如果 p、q 分别在 cur 的不同子树中，那么 cur 就是首个共同祖先，返回
- 否则，如果 p、q 都在 cur 的左子树中，那么 cur 指向左孩子节点，否则指向右孩子节点

缺点：在上面的循环中，判定在左、右子树中会重复遍历一些节点

/**
 * 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(root == node || isTreeNode(root->left, node) || isTreeNode(root->right, node))
            return true;
        else
            return false;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(p->left == q || p->right == q)
            return p;
        if(q->left == p || q->right == p)
            return q;

        // 首个共同祖先 ancestor：p、q 都在以 ancestor 为根节点的树中，且分别在左右子树（ancestor 也可以算左 or 右子树的节点）
        TreeNode* cur = root;
        while(cur != NULL)
        {
            bool pInLeft = (p == cur) || isTreeNode(cur->left, p);
            bool qInLeft = (q == cur) || isTreeNode(cur->left, q);
            bool pInRight = (p == cur) || !pInLeft;
            bool qInRight = (q == cur) || !qInLeft;
            // cout << cur->val << " " << pInLeft << " " << qInLeft << endl;
            if((pInLeft && qInRight) || (pInRight && qInLeft))
                return cur;

            if(pInLeft && qInLeft)
                cur = cur->left;
            else
                cur = cur->right;
        }
        return NULL;
    }
};

执行结果：

执行结果：通过

执行用时：20 ms, 在所有 C++ 提交中击败了 62.90% 的用户
内存消耗：13.7 MB, 在所有 C++ 提交中击败了 98.47% 的用户

解法二

/**
 * 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 or q，因此无共同祖先，返回 NULL
        if(root == NULL)
            return NULL;
        // 递归结束条件 2：找到了 p or q 节点其中一个，就返回该节点
        if(root == p || root == q)
            return root;

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

        // 如果 p、q 节点分别在不同子树中，则当前 root 节点就是首个共同祖先
        if(left != NULL && right != NULL)
            return root;
        // 如果左子树中找到了一个节点（left：p、q 节点中的一个），而右子树中没有，则说明另一个节点也在左子树，且 left 就是首个共同祖先
        // - 如果左子树中找到并返回的节点是 p（left == p），而右子树中既无 o 也无 q，则说明 q 是 p 的子孙节点，因此还未遍历到，所以 p 是首个共同祖先
        // - 同理，如果左子树中找到并返回的节点是 q, 则 q 是首个共同祖先
        else if(left != NULL && right == NULL)
            return left;
        // 如果右子树中找到了一个节点（right：p、q 节点中的一个），而左子树中没有，则说明另一个节点也在右子树，且 right 就是首个共同祖先
        else
            return right;
    }
};

执行结果：

执行结果：通过

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

《程序员面试金典（第 6 版）》

[中等] 4.8 首个共同祖先

题目

解答 & 代码

解法一

解法二