树中两个叶子节点的最近公共祖先(LCA)代码异常排查求助

我帮你找出了代码里几个关键问题，导致它无法稳定运行：

• 迭代器未同步递增：在两个分支的while循环中，你只对其中一个迭代器做了++操作，另一个完全停在初始位置。比如第一个分支里，it2始终不动，和it1遍历的每个元素逐一比较，这显然不可能找到正确的公共祖先。
• 错误覆盖最近公共祖先：每次找到相等节点就更新common_ancestor，最终会得到最远的公共祖先（比如根节点），而我们需要的是第一个遇到的、离叶子最近的公共祖先，找到后应该立即终止循环。
• 对齐逻辑方向错误：你用ancestors2.end() - t来对齐迭代器，但你的祖先列表是按「直接父→祖父→根」的顺序存储的，更长列表的前面部分才是独有的祖先，应该从begin() + diff的位置开始对齐，而不是从末尾往前偏移。
• （可选）未包含节点自身：虽然题目限定是两个叶子节点，但如果两个叶子是同一个节点（边界情况），或者LCA是其中一个节点本身时，你的代码会漏掉这种场景，把节点自身加入祖先列表能让逻辑更通用。

修复后的代码方案 #

方案1：用反向迭代器（更直观，推荐） #

这种方式不需要手动处理列表长度差异，反向迭代器会自动从根节点开始往叶子方向遍历，最后记录的相等节点就是最近公共祖先：

Node* findLCA(Node* node1, Node* node2) {
    std::vector<Node*> ancestors1;
    std::vector<Node*> ancestors2;

    // 收集node1的所有祖先（包含自身）
    Node* temp_node = node1;
    while(temp_node != nullptr) {
        ancestors1.push_back(temp_node);
        temp_node = temp_node->parent;
    }

    // 收集node2的所有祖先（包含自身）
    temp_node = node2;
    while(temp_node != nullptr) {
        ancestors2.push_back(temp_node);
        temp_node = temp_node->parent;
    }

    Node* common_ancestor = nullptr;
    // 用反向迭代器从根节点开始往叶子方向遍历
    auto it1 = ancestors1.rbegin();
    auto it2 = ancestors2.rbegin();

    while(it1 != ancestors1.rend() && it2 != ancestors2.rend()) {
        if (*it1 == *it2) {
            // 记录当前公共祖先，继续寻找更近的
            common_ancestor = *it1;
        } else {
            // 遇到不相等节点，说明上一个记录的就是最近公共祖先
            break;
        }
        ++it1;
        ++it2;
    }

    // 如果common_ancestor为nullptr，说明两个节点不在同一棵树中
    return common_ancestor;
}

方案2：修正正向迭代器逻辑 #

如果你更倾向于原来的正向迭代器思路，这里是修正后的版本：

Node* findLCA(Node* node1, Node* node2) {
    std::vector<Node*> ancestors1;
    std::vector<Node*> ancestors2;

    // 收集node1的所有祖先（包含自身）
    Node* temp_node = node1;
    while(temp_node != nullptr) {
        ancestors1.push_back(temp_node);
        temp_node = temp_node->parent;
    }

    // 收集node2的所有祖先（包含自身）
    temp_node = node2;
    while(temp_node != nullptr) {
        ancestors2.push_back(temp_node);
        temp_node = temp_node->parent;
    }

    Node* common_ancestor = nullptr;
    size_t size1 = ancestors1.size();
    size_t size2 = ancestors2.size();

    if (size1 < size2) {
        size_t diff = size2 - size1;
        auto it1 = ancestors1.begin();
        auto it2 = ancestors2.begin() + diff;
        while(it1 != ancestors1.end()) {
            if (*it1 == *it2) {
                common_ancestor = *it1;
                // 找到最近公共祖先，立即终止循环
                break;
            }
            ++it1;
            ++it2; // 同步递增两个迭代器
        }
    } else {
        size_t diff = size1 - size2;
        auto it2 = ancestors2.begin();
        auto it1 = ancestors1.begin() + diff;
        while(it2 != ancestors2.end()) {
            if (*it1 == *it2) {
                common_ancestor = *it1;
                break;
            }
            ++it1; // 同步递增两个迭代器
            ++it2;
        }
    }

    return common_ancestor;
}

内容的提问来源于stack exchange，提问作者General Gravicius