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

1. 递归搜索

设问题为LCA(root, o1, o2), 该问题有以下递归性质：

  • 如果o1和o2都在root的左子树中，那么LCA(root, o1, o2) = LCA(root->left, o1, o2).
  • 如果o1和o2都在root的右子树中，那么LCA(root, o1, o2) = LCA(root->right, o1, o2).
  • 如果一个在左子树，一个在右子树，显然root就是答案！

以上关系可以用下图表示（情形1,2对称，只画了一种情况）：
图片说明

据此设计如下递归算法，由于函数参数的问题，需要增加一个以TreeNode*为返回值的辅助函数：

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    TreeNode* LCA(TreeNode* r, int o1, int o2) {
        if (!r) return NULL;
        if (r->val == o1 || r->val == o2) return r;

        TreeNode* ln = LCA(r->left, o1, o2);
        TreeNode* rn = LCA(r->right, o1, o2);

        if (!ln) return rn;
        if (!rn) return ln;

        return r;
    }

    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        TreeNode* lca = LCA(root, o1, o2);
        return lca->val;
    }
};
  • 时间复杂度：对于n个点的二叉树，对每个节点都要遍历一遍，时间复杂度是O(n)。
  • 空间复杂度：对于数据比较好的情况，即接近完全二叉树的情况下，会递归logn次，最差情况下会退化为链表，递归n次，故空间复杂度平均是O(logn)，最差是O(n).

2. 非递归的层序遍历

LCA问题还有这样一个性质：

root到o1的路径和root到o2的路径的第一个交点即为所求。

这道题如果不用递归的办法来做，还可以有如下做法：

  1. 通过bfs，层序遍历这棵树，记录每个节点的父节点，因为o1和o2的孩子与本题无关，所以只需遍历到o1和o2就可以了。
  2. 从o1开始，跑出o1到root的路径。
  3. 从o2开始，往o2的父亲逆向遍历找，如果某个点位于o1到root的路径中，则该点即为答案
  4. 如果走到root也没找到，说明root是答案。 
/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    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)，用到了常数个最大长度为n的标准容器。