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

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // 使用哈希表存储每个节点的父节点
        unordered_map<int, TreeNode*> parentMap;

        // 使用队列进行BFS遍历
        queue<TreeNode*> q;
        q.push(root);
        parentMap[root->val] = nullptr; // 根节点没有父节点

        // BFS遍历树，记录每个节点的父节点
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();

            if (node->left != nullptr) {
                parentMap[node->left->val] = node;
                q.push(node->left);
            }

            if (node->right != nullptr) {
                parentMap[node->right->val] = node;
                q.push(node->right);
            }
        }

        // 存储o1的所有祖先节点
        unordered_set<int> ancestors;
        int current = o1;

        // 从o1向上回溯到根节点，记录所有祖先
        while (current != -1) {
            ancestors.insert(current);
            TreeNode* parent = parentMap[current];
            if (parent == nullptr) {
                break;
            }
            current = parent->val;
        }

        // 如果o2本身就是o1的祖先，直接返回o2
        if (ancestors.find(o2) != ancestors.end()) {
            return o2;
        }

        // 从o2向上回溯，直到找到第一个在o1祖先集合中的节点
        TreeNode* parentOfO2 = parentMap[o2];
        while (parentOfO2 != nullptr) {
            if (ancestors.find(parentOfO2->val) != ancestors.end()) {
                return parentOfO2->val;
            }
            parentOfO2 = parentMap[parentOfO2->val];
        }

        return -1; // 理论上不会执行到这里，因为根节点一定是公共祖先
    }
};

// 辅助函数：根据层序遍历数组构建二叉树
TreeNode* buildTree(const vector<int>& nodes) {
    if (nodes.empty() || nodes[0] == -1) return nullptr;

    TreeNode* root = new TreeNode(nodes[0]);
    queue<TreeNode*> q;
    q.push(root);

    int i = 1;
    while (!q.empty() && i < nodes.size()) {
        TreeNode* current = q.front();
        q.pop();

        // 左子节点
        if (i < nodes.size() && nodes[i] != -1) {
            current->left = new TreeNode(nodes[i]);
            q.push(current->left);
        }
        i++;

        // 右子节点
        if (i < nodes.size() && nodes[i] != -1) {
            current->right = new TreeNode(nodes[i]);
            q.push(current->right);
        }
        i++;
    }

    return root;
}

1.利用BFS记录每个节点的父节点,使用哈希表(unordered_set)存储每个节点的父节点
2.使用哈希表存储o1的所有祖先节点
3.分两种情况
3.1如果o2本身就是o1的祖先，直接返回o2
3.2从o2向上回溯，直到找到第一个在o1祖先集合中的节点