题解 | #在二叉树中找到两个节点的最近公共祖先#

JZ86 在二叉树中找到两个节点的最近公共祖先

题目描述

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

方法一：递归思想

解题思路

针对方法一，我们采用递归的思想进行解决。我们思考，如果o1和o2都在root的左子树中，则对左子树进行递归。如果o1和o2都在root的右子树中，则对右子树进行递归。如果o1在左边，o2在右边，或者o1在右边，o2在左边，则root即为公共祖先点。因此按照上述的规则进行递归，然后对其进行求解即可。

解题代码

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        return helper(root, o1, o2)->val;
    }
    TreeNode* helper(TreeNode* root, int o1, int o2)
    {
        if(root == NULL || root->val == o1 || root->val == o2)
        {
            return root;
        }
        TreeNode* left = helper(root->left, o1, o2);
        TreeNode* right = helper(root->right, o1, o2);
        if(left == NULL) return right;
        if(right == NULL) return left;
        return root;
    }
};

复杂度分析

时间复杂度：n个节点都需要遍历，因此时间复杂度为$O(N)O(N)$。

空间复杂度：取决于递归的栈深，在最差的情况下，二叉树退化为链表，树高为n，因此空间复杂度为$O(N)O(N)$

方法二：层次遍历方法

解题思路

我们也可以使用层次遍历的方法，首先通过广度优先记录每个节点的父节点，然后从o1开始，记录o1到root的路径，然后从o2开始，往其父节点开始寻找，如果节点在o1到root的路径里面且是第一次出现的，则输出结果，否则继续，直到root节点。

解题代码

class Solution {
public:
    typedef TreeNode *pNode;
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // 记录每个节点的父亲
        unordered_map<int, int> f;
        // 记录bfs队列
        queue<pNode> q;
        q.push(root);
        // 找到o1和o2的父节点就可以停止了
        while (!f[o1] || !f[o2]) {
            pNode cur = q.front();
            q.pop();
            pNode l = cur->left, r = cur->right;
            // 如果当前点有左孩子，那么记录下左孩子的父子关系，并且加入队列
            if (l) 
                f[l->val] = cur->val, q.push(l);
            // 右侧对称
            if (r) 
                f[r->val] = cur->val, q.push(r);
        }
        // path记录root到o1的路径，无序即可
        unordered_set<int> path;
        while (f[o1]) {
            path.insert(o1);
            o1 = f[o1];
        }
        // 找到o2到root的路径中，第一个跟path有交集的点，即为答案
        while (path.find(o2) == path.end() && o2 != root->val) {
            o2 = f[o2];
        }
        return o2;
    }
};

复杂度分析

时间复杂度：遍历n个节点，因此时间复杂度为$O(N)O(N)$

空间复杂度：使用队列辅助空间，因此空间复杂度为$O(N)O(N)$