面试题68：树中两个节点的最低公共祖先

先按二叉搜索树、父指针树与普通多叉树澄清结构，再用根到目标的回溯路径忠实还原作者的严格公共父节点算法。

学习目标

  • 能根据树的结构（BST/父指针/普通多叉树）选择对应 LCA 算法
  • 能用路径回溯法在普通树中找到两个节点的最低公共祖先
  • 能处理缺失节点、根节点与相同节点等边界

从“这棵树到底有什么信息”开始

“树中两个节点的最低公共祖先”看似是固定算法题，实际第一句话应是询问树的结构。它是二叉搜索树吗？节点有父指针吗？只有从根到孩子的单向连接吗？目标节点保证在树中吗？“祖先”是否允许节点自身？

这些答案会改变可用信息和最优路径。直接写常见的二叉树递归LCA，只覆盖了其中一种定义，也完全没有还原作者源码中的普通多叉树与路径列表。原章的核心面试能力是。

树结构可用信息转化答案位置复杂度
二叉搜索树左右孩子 + 有序键比较两个目标值与当前值首个落在两值区间内的节点O(h) / O(1)
有父指针的树每个节点可向父亲移动把两条上行链视为链表对齐深度后首个相同节点O(h) / O(1)
普通树，无父指针只有根和孩子列表分别保存根到目标的路径两条路径最后公共节点O(n) / O(h)
先澄清节点结构，再选择有序下行、父链对齐或根路径比较。

先预测作者的链式测试：1连到2，2连到3，3连到4，4连到5，查询节点5与4。常见“祖先可包含自身”的LCA会返回4，但作者期望3。原因不是源码偶然出错，而是作者保存的路径不包含目标节点，求的是严格位于两个目标上方的公共父节点。

三种结构，三条解题路线

利用大小关系

若是二叉搜索树，设两个目标键的较小者为low、较大者为high。从根向下：

  1. 当前键同时大于high，两个目标都在左子树，向左。
  2. 当前键同时小于low，两个目标都在右子树，向右。
  3. 当前键落在low与high之间，两个目标从这里分居两侧，当前节点就是汇合点。

这就是“二叉搜索树利用大小关系”。不必遍历无关分支，时间O(h)，迭代额外空间O(1)。但它依赖有序性、键的比较规则和目标确实属于同一棵树；普通树不能套用。

const BstNode* lowestCommonAncestor(
    const BstNode* root,
    const BstNode* first,
    const BstNode* second) {
    if (!root || !first || !second)
        return nullptr;
 
    const int low =
        std::min(first->value, second->value);
    const int high =
        std::max(first->value, second->value);
 
    const BstNode* current = root;
    while (current) {
        if (current->value > high) {
            current = current->left;
        } else if (current->value < low) {
            current = current->right;
        } else {
            return current;
        }
    }
    return nullptr;
}

若题目要求作者式“严格父节点”，且一个目标恰好是另一个的祖先，上面的含自身版本还需调整。面试中不能只说LCA三个字，必须用祖先与后代样例固定定义。

有父指针时转化为链表公共节点

若每个节点都有parent，目标到根分别形成两条单链。“有父指针时转化为链表公共节点”：可以记录两条上行路径再比较，也可以先计算深度，让较深节点先上移深度差，然后两个指针同步向父亲移动，首次相同处就是答案。

const ParentNode* commonAncestor(
    const ParentNode* first,
    const ParentNode* second) {
    if (!first || !second)
        return nullptr;
 
    auto depth = [](const ParentNode* node) {
        std::size_t result = 0;
        for (; node; node = node->parent)
            ++result;
        return result;
    };
 
    std::size_t leftDepth = depth(first);
    std::size_t rightDepth = depth(second);
    while (leftDepth > rightDepth) {
        first = first->parent;
        --leftDepth;
    }
    while (rightDepth > leftDepth) {
        second = second->parent;
        --rightDepth;
    }
    while (first != second) {
        first = first->parent;
        second = second->parent;
    }
    return first;
}

两条父链的尾部是共同的根侧后缀，和链表第一个公共节点同构。时间O(h)，额外空间O(1)。若两节点来自不同树，两个指针最终同时成为nullptr；若要严格父节点，可从first->parent与second->parent开始。

普通树保存根到节点的路径

作者面对的是没有parent的普通树：TreeNode只有m_nValue和m_vChildren，可有任意数量孩子。无法从目标向上走，只能从根分别找到目标，保存两条祖先路径，再取最后一个相同节点。这就是“普通树保存根到节点的路径”。

两条根路径最后公共的节点即最低公共父节点12345678910目标 6目标 8路径1：1,2,4,6路径2：1,2,5,8最后公共 = 2同步扫描两条根路径，用 pLast 保存最近一次身份相同的节点；路径在 4/5 分叉后不会重新汇合。O(n) 时间、O(h) 空间。
作者 Test1 的普通多叉树：目标 6 与 8 的两条祖先路径在节点 2 后分叉。

Test1中根1的孩子是2、3；2的孩子是4、5；4的孩子是6、7；5的孩子是8、9、10。查询6与8时，路径分别是1、2、4和1、2、5，最后公共节点为2。

如何只保留成功分支

GetNodePath进行深度优先搜索。当前根就是目标时直接返回true；否则先把当前节点压入path，再依次递归孩子。某个孩子找到目标就停止继续搜索；所有孩子都失败时，弹出刚压入的当前节点并返回false。

这种“选择节点、递归尝试、失败撤销”的方式称为。函数返回true时，path里只留下根到目标之前的节点，不含目标自身。

bool GetNodePath(
    const TreeNode* root,
    const TreeNode* target,
    std::list<const TreeNode*>& path) {
    if (root == target)
        return true;
 
    path.push_back(root);
    bool found = false;
 
    auto child = root->m_vChildren.begin();
    while (!found
           && child < root->m_vChildren.end()) {
        found = GetNodePath(
            *child, target, path);
        ++child;
    }
 
    if (!found)
        path.pop_back();
    return found;
}
 
const TreeNode* GetLastCommonNode(
    const std::list<const TreeNode*>& path1,
    const std::list<const TreeNode*>& path2) {
    auto first = path1.begin();
    auto second = path2.begin();
    const TreeNode* last = nullptr;
 
    while (first != path1.end()
           && second != path2.end()) {
        if (*first == *second)
            last = *first;
        ++first;
        ++second;
    }
    return last;
}
 
const TreeNode* GetLastCommonParent(
    const TreeNode* root,
    const TreeNode* node1,
    const TreeNode* node2) {
    if (!root || !node1 || !node2)
        return nullptr;
 
    std::list<const TreeNode*> path1;
    GetNodePath(root, node1, path1);
    std::list<const TreeNode*> path2;
    GetNodePath(root, node2, path2);
    return GetLastCommonNode(path1, path2);
}

上面保持作者逻辑和接口。它假设递归收到的孩子指针非空，且结构确实是无环树；如果m_vChildren含nullptr会解引用空指针，如果输入是有环图则可能无限递归。工程版本应在递归入口检查root，并对非树结构使用visited集合。

两条路径为什么只需同步扫描

根到任意节点的路径唯一，因此两条路径的公共部分必然是从根开始的一段。同步从path1和path2开头比较，每次相同就更新pLast；首次不同之后，在合法树中不会再次出现同一节点。

作者循环在不同时没有break，而是继续前进。对合法树不会影响答案，因为两条根路径一旦分叉便不能重新汇合；若能重新汇合，输入实际是共享子节点的有向无环图，不再满足树的唯一父节点性质。现代实现可以在首次不同时break，让这个不变式更清楚。

比较使用节点指针而不是m_nValue，这是。两个不同节点即使都存数字2，也不是公共节点。作者的算法比较指针是正确的，但测试辅助函数只比较结果值；若树中允许重复值，测试可能把错误节点误判为通过，应改为直接比较pResult与pExpected。

最低公共祖先与严格公共父节点

作者文件名和函数名使用CommonParent，GetNodePath又在命中目标前返回，明确排除了目标自身。由此形成语义。

对比项常见含自身 LCA作者源码的严格父节点
查询节点5 与 45 与 4
路径是否含目标包含：1,2,3,4,5 / 1,2,3,4排除：1,2,3,4 / 1,2,3
答案43
问题定义最低公共祖先：节点可作自身祖先最低公共父节点：必须严格位于目标上方
作者 Test2不会采用期望节点 3
是否把目标自身放进路径会改变祖先与后代查询的答案，必须先固定定义。

链1到2到3到4到5中，查询5与4：

  • 节点5的祖先路径是1、2、3、4。
  • 节点4的祖先路径是1、2、3。
  • 最后公共节点是3，正是作者Test2的期望。

常见LCA定义允许节点作为自身祖先，则答案会是4。现有旧页面采用“root等于p或q就返回root”的二叉递归，得到的是含自身LCA，既改变了约定，也改变了树结构。重建后的页面同时讲清两种定义，但作者代码与官方测试以严格父节点为准。

缺失节点、根节点与相同节点

GetLastCommonParent先拒绝空根或空目标。目标不在树中时，GetNodePath会逐层回溯，把path恢复为空；空路径与任何路径都没有公共节点，因此返回nullptr。作者虽然忽略两个布尔返回值，最终结果仍是nullptr，但显式检查found会更清楚。

如果查询目标之一就是根，命中时路径为空。由于作者不把目标放入路径，根不可能成为自己的严格父节点，结果为nullptr。查询两个相同的非根节点时，两条路径相同，返回该节点的父亲；查询根与根仍返回nullptr。

const TreeNode* strictCommonParent(
    const TreeNode* root,
    const TreeNode* first,
    const TreeNode* second) {
    if (!root || !first || !second)
        return nullptr;
 
    std::vector<const TreeNode*> left;
    std::vector<const TreeNode*> right;
    if (!getAncestorPath(
            root, first, left)
        || !getAncestorPath(
            root, second, right)) {
        return nullptr;
    }
 
    const TreeNode* last = nullptr;
    const std::size_t common =
        std::min(left.size(), right.size());
    for (std::size_t i = 0;
         i < common && left[i] == right[i];
         ++i) {
        last = left[i];
    }
    return last;
}

现代版本应让getAncestorPath在入口处理空指针，并明确它在命中目标前返回、不把目标压入vector。两次搜索最坏各访问整棵树，时间O(n)；两条路径和递归栈都至多O(h)。在极度退化的链上h等于n，递归可能栈溢出，可改为显式栈DFS。

四组官方测试逐项复现

Test1检查普通分叉多叉树中不同子树的公共父节点2。Test2把树退化成单链，专门锁定“节点4不能作为自身父节点”，所以5与4返回3。Test3创建独立节点6但不连接进树，验证树外目标返回nullptr。Test4把根和两个目标都设为nullptr，验证入口防御。

测试仍有两个局限。第一，Test函数用节点值比较结果与期望，重复值时不可靠；第二，各测试创建节点后没有调用DestroyTree，示例进程结束时由操作系统回收，但长期测试应释放内存。它们不改变算法答案，却是代码审查时应指出的工程问题。

验证还应增加：两节点相同、其中一个是根、孩子vector含空指针、重复值但不同身份、极深链，以及非法共享子节点结构。测试的目的不仅是得到一个值，还要证明输入契约和算法假设一致。

先澄清结构再选择算法

“先澄清树的结构再选择算法”可以整理为固定面试流程：

本章练习

练习

问题 1： 找最低公共祖先前必须先澄清什么？

问题 2： 普通多叉树用什么方法找 LCA？

问题 3： 节点不在树中时如何处理？

概念说明

本章核心概念：先澄清树的结构再选择算法。理解这些概念是掌握解题方法的关键，具体实现与边界条件请参考上文对应小节。

本章回顾

  1. 最低公共祖先没有脱离结构的唯一模板，首先要询问有序性、父指针、孩子数量和成员保证。
  2. 二叉搜索树可利用大小关系单路下行，首个落在两目标值区间的节点就是汇合点。
  3. 有父指针时可转化为两条链表，先对齐深度再同步向根移动。
  4. 作者处理没有父指针的普通多叉树，分别保存根到两个目标之前的祖先路径。
  5. GetNodePath通过压入、递归和失败弹出实现路径回溯。
  6. 两条根路径的公共部分必为公共前缀，最后相同节点就是最低公共父节点。
  7. 作者路径排除目标自身，因此5与4在链上返回3，而常见含自身LCA会返回4。
  8. 算法按节点身份比较正确，作者测试按值比较则可能在重复值树中误报。
  9. 两次搜索时间O(n)，路径与递归栈空间O(h)；空输入或树外节点返回nullptr。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

澄清结构
编写 LCA 算法前先确认树的具体类型与约束。
二叉搜索树
左子树值 < 根值 < 右子树值，可利用大小关系找 LCA。
路径回溯
保存根到节点的路径，逐层回溯找公共祖先。
复习本章（5 题）

讨论

评论区加载中…