二叉树的最近公共祖先

二叉树的最近公共祖先

一、题目

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

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

进阶问题：如果查询两个节点的最近公共祖先的操作十分频繁，想法让单条查询的时间减少。

leetcode：https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

二、思路

给定的两个节点一个为 p，一个为 q
当前节点记为 cur，他的左子树记为 left，他的右子树记为 right
我们需要 left 和 right 的值来做逻辑判断，因此很适合用后序遍历。

1. 左右子树在遍历的过程中，如果遇到 p 或者 q 或者 null，直接返回 p 或者 q 或者 null
2. 左右子树都返回 null，则说明 cur 的整颗树上都没有发现 p 或者 q，返回 null
3. 左右子树都返回不为空，则说明 cur 的树上发现了 p 或者 q。cur 就是公共祖先节点
4. 左右子树有一个返回不为空，要么发现了 p 或者 q，要么 cur 已经是最近的公共祖先节点，直接返回 cur 即可

三、code

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    explicit TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || root == p || root == q) {
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left != nullptr && right != nullptr) {
            return root;
        }
        return left != nullptr ? left : right;
    }
};

N 是二叉树的节点树。二叉树上的所有节点有且只会被访问一次，因此时间复杂度：O(n)

因为 N 是二叉树的节点数，递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下是一条链，此时高度为 N，所以空间复杂度：O(n)

四、更快的时间复杂度

直接建立任意两个节点之间的最近公共祖先记录，便于以后查询。建立记录的具体过程如下：

1. 对二叉树中的每颗子树（一共 N 课树）都进行如下步骤
2. 假设子树的头节点为 h，h 所有的后代节点和 h 节点的最近公共祖先都是 h，记录下来。h 左子树的每个节点和 h 右子树的每个节点的最近公共祖先都是 h，记录下来

class Helper {
public:
    explicit Helper(TreeNode* head) {
        init_map(head);
        set_map(head);
    }

    TreeNode* query(TreeNode* node1, TreeNode* node2) {

        // for (const auto& x : mp_) {
        //     for (const auto& y : x.second) {
        //         std::cout << x.first->val << " " << y.first->val << " " << y.second->val << std::endl;
        //     }
        // }

        if (node1 == node2) {
            return node1;
        }
        auto node1_iter = mp_.find(node1);
        if (node1_iter != mp_.end()) {
            auto node2_iter = (*node1_iter).second.find(node2);
            if (node2_iter != (*node1_iter).second.end()) {
                return (*node2_iter).second;
            }
        }

        auto iter2 = mp_.find(node2);
        if (iter2 != mp_.end()) {
            auto iter1 = (*iter2).second.find(node1);
            if (iter1 != (*iter2).second.end()) {
                return (*iter1).second;
            }
        }
        return nullptr;
    }

private:
    void init_map(TreeNode* head) {
        if (head == nullptr) return;
        mp_[head] = std::unordered_map<TreeNode*, TreeNode*>();
        init_map(head->left);
        init_map(head->right);
    }

    void set_map(TreeNode* head) {
        if (head == nullptr) return;
        head_record(head->left, head);
        head_record(head->right, head);
        sub_record(head);
        set_map(head->left);
        set_map(head->right);
    }

    void head_record(TreeNode* node, TreeNode* head) {
        if (node == nullptr) return;
        mp_[node][head] = head;
        head_record(node->left, head);
        head_record(node->right, head);
    }

    void sub_record(TreeNode* head) {
        if (head == nullptr) return;
        pre_left(head->left, head->right, head);
        sub_record(head->left);
        sub_record(head->right);
    }

    void pre_left(TreeNode* left, TreeNode* right, TreeNode* head) {
        if (left == nullptr) {
            return;
        }
        pre_right(left, right, head);
        pre_left(left->left, right, head);
        pre_left(left->right, right, head);
    }

    void pre_right(TreeNode* left, TreeNode* right, TreeNode* head) {
        if (right == nullptr) return;
        mp_[left][right] = head;
        pre_right(left, right->left, head);
        pre_right(left, right->right, head);
    }

private:
    std::unordered_map<TreeNode*, std::unordered_map<TreeNode*, TreeNode*>> mp_;
};

class Solution2 {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        Helper helper(root);
        return helper.query(p, q);
    }
};

二叉树的节点数为 N，想要记录每个节点之间的信息，信息的条数为 ((N-1)*N)/2。所以建立如上结构的空间复杂度 O(N^2)，时间复杂度为 O(N^2)，单次查询的时间复杂度为 O(1)