面试题54：二叉搜索树的第k大节点（源码按第k小）

以中序遍历和引用计数器寻找二叉搜索树升序序列中的第k个节点，并辨明题面第k大与作者源码第k小的差异。

学习目标

  • 能用中序遍历与引用计数器寻找二叉搜索树第 k 个节点
  • 能解释 k 为什么必须按引用传递（跨递归共享计数）
  • 能辨明题面"第 k 大"与作者源码"第 k 小"的差异

从“第1个到底是5还是11”开始

先预测：二叉搜索树根为8，左子树是6、5、7，右子树是10、9、11。如果题目说“二叉搜索树的第k大节点”，k等于1通常应想到最大值11；但作者仓库的函数对k等于1返回5。

原因在于源码使用左子树、根、右子树的。对二叉搜索树，这个次序得到5、6、7、8、9、10、11，作者从最小端开始计数。

BST 中序 = 递增序列：第 k 小即中序第 k 个861057911中序遍历（左→根→右）：5第16第27第38第49第510第611第7k=4 → 中序第 4 个 = 8（命中后 9、10、11 不再访问）k 由引用在递归层共享递减；k=1 返回最小节点 5；k=0 或越界返回空。O(h+k) 时间、O(h) 栈。
二叉搜索树中序遍历得到 5 到 11 的有序节点序列；作者的 k=1 返回 5。

因此本章必须同时保留两层事实：

  1. 作者题面注释写的是“第k大的结点”，质量清单也称“二叉搜索树的第k大节点”。
  2. 可执行源码和全部断言实际求升序中的第k个，也就是第k小节点。

本页以源码和测试定义主算法，同时单独给出真正第k大应如何改。这样既不掩盖原材料矛盾，也不把相反遍历冒充作者实现。

中序顺序就是

二叉搜索树满足左子树键小于当前键、右子树键大于当前键。递归访问左子树会先输出所有较小键，随后输出当前键，再由右子树输出所有较大键。由归纳可知整棵树的中序结果是。

在作者的唯一键测试树中，序列严格递增。只需沿该序列数节点，计数到第k个节点时返回，不必把全部值复制到数组，也不必额外排序。

以k等于4为例，访问5前k为4，处理后减为3；访问6前为3，处理后减为2；访问7前为2，处理后减为1；访问8时发现k等于1，8就是答案。

这里k采用从1开始的。k等于0不是第一个，而是非法输入。

为什么 k 必须按

每个递归调用都属于同一次中序序列扫描。左子树访问了多少节点，根和右子树必须接着使用剩余排名，而不是重新从原始k开始。

作者让核心函数接收unsigned int引用。这个跨层共享并持续递减的变量称为。

如果k按值传递，左子树内部的递减不会反馈给父调用。父节点仍以旧k判断，多个子树会各自从头计数，结果错误。另一种正确设计是让递归函数同时返回“是否命中”和“已访问数量”，但结构更复杂。

阶段 1
递归左子树
先取得更小节点
target 可能被左侧设置
阶段 2
检查 target
非空则直接回传
阻止重复递减 k
阶段 3
访问当前节点
k 为 1 时命中
否则 k 减 1
阶段 4
递归右子树
仅 target 仍为空时进入
继续较大节点
k 通过引用在所有递归层共享；target 非空后沿调用栈回传并停止后续遍历。

target也承担停止信号。左子树已经找到目标时，父层不再处理当前节点；当前节点命中后，不再进入右子树。这种避免遍历剩余较大节点。

忠实还原作者递归

外层KthNode负责检查空根和k等于0，保证核心函数拿到非空节点与正计数。

const BinaryTreeNode* KthNodeCore(
    const BinaryTreeNode* pRoot,
    unsigned int& k);
 
const BinaryTreeNode* KthNode(
    const BinaryTreeNode* pRoot,
    unsigned int k) {
    if (pRoot == nullptr || k == 0) {
        return nullptr;
    }
    return KthNodeCore(pRoot, k);
}
 
const BinaryTreeNode* KthNodeCore(
    const BinaryTreeNode* pRoot,
    unsigned int& k) {
    const BinaryTreeNode* target = nullptr;
 
    if (pRoot->m_pLeft != nullptr) {
        target =
            KthNodeCore(pRoot->m_pLeft, k);
    }
 
    if (target == nullptr) {
        if (k == 1) {
            target = pRoot;
        }
        --k;
    }
 
    if (target == nullptr &&
        pRoot->m_pRight != nullptr) {
        target =
            KthNodeCore(pRoot->m_pRight, k);
    }
    return target;
}

访问当前节点时先判断k是否为1，再执行递减。命中节点后k变为0，但target已经非空；所有父层的target检查会阻止再次递减，所以unsigned不会在正常路径下从0下溢。

若k大于节点总数，每个节点都访问一次，k只减去节点数，最终仍为正，target保持空并返回nullptr。k等于0则在外层被拒绝，从不进入核心。

核心函数本身会直接解引用pRoot，不能对它单独传nullptr。这个前置条件由外层与“只有子指针非空才递归”的两个判断共同维持。

旧页提前退出条件为何错误

旧页示例写成“节点为空或答案为空时返回”。但答案初始本来就是nullptr，所以第一次调用便会返回，整个函数永远不访问树。

正确条件应是“节点为空或答案已经非空时返回”：

void inOrder(
    const BinaryTreeNode* node,
    unsigned int& k,
    const BinaryTreeNode*& answer) {
    if (node == nullptr ||
        answer != nullptr) {
        return;
    }
 
    inOrder(node->m_pLeft, k, answer);
    if (answer != nullptr) {
        return;
    }
 
    if (k == 1) {
        answer = node;
        return;
    }
    --k;
    inOrder(node->m_pRight, k, answer);
}

这个修正版与作者target局部返回值的控制流等价，但作者原写法无需额外answer引用。

题面第k大与源码第k小

维度作者实现含义边界
排名起点k 从 1 开始k=1 是最小节点k=0 返回空
遍历方向左、根、右结果按升序源码实际求第 k 小
超出节点数遍历结束仍未命中返回 nullptrk 保持正数
共享状态unsigned int 引用跨递归层递减命中后不可再减
树形平衡、左链、右链结果语义相同栈深度由高度决定
空树根为 nullptr入口直接返回空核心函数不接收空根
复杂度访问前 k 个节点及路径O(h+k) 时间O(h) 递归栈
题面“第 k 大”与源码升序计数不一致；本表按可执行代码和断言定义行为。

作者TestA对完整树依次断言k为1到7时返回5到11。纯左链和纯右链也都断言1到5升序返回。因此“源码按第k小”不是推测，而是28个断言中的明确行为。

真正寻找第k大只需镜像遍历：先右子树，再当前节点，最后左子树。共享计数器和提前终止逻辑保持不变。

const BinaryTreeNode* KthLargestCore(
    const BinaryTreeNode* node,
    unsigned int& k) {
    if (node == nullptr) {
        return nullptr;
    }
 
    if (const BinaryTreeNode* target =
            KthLargestCore(
                node->m_pRight, k)) {
        return target;
    }
 
    if (k == 1) {
        return node;
    }
    --k;
    return KthLargestCore(
        node->m_pLeft, k);
}
 
const BinaryTreeNode* KthLargest(
    const BinaryTreeNode* root,
    unsigned int k) {
    if (root == nullptr || k == 0) {
        return nullptr;
    }
    return KthLargestCore(root, k);
}

对示例树，这个版本k等于1返回11，k等于4返回8，k等于7返回5。不要只改函数名而保留中序方向。

复杂度不是永远O(log n)

设树高为h。找到第k小节点前，算法需要沿路径下降并完成前k次中序访问，时间可写为O(h加k)，最坏仍为O(n)。当k接近节点数，几乎整棵树都会被访问。

递归栈空间为O(h)。平衡树高度O(log n)，极端左链或右链高度O(n)。作者专门构造TestB纯左链和TestC纯右链，既验证次序，也覆盖最深递归形态。

普通二叉搜索树节点没有子树大小，无法仅凭一次键比较确定排名在哪棵子树。若节点额外维护左子树节点数leftSize，可以在每层比较k与leftSize加1，以O(h)时间选择方向；这属于顺序统计树扩展，不是作者结构。

是否值得维护leftSize取决于查询与修改比例。只做一次排名查询时，中序计数不改变节点结构，也没有额外持久存储；若同一棵树要回答大量不同k，反复遍历前缀会重复工作，子树大小能把每次查询降为沿一条根到叶路径。代价是插入、删除和旋转时必须同步更新沿途计数，任何一次漏更新都会让后续排名静默出错。

也可以只做一次完整中序遍历，把节点指针缓存为数组。预处理时间和空间均为O(n)，之后第k小可O(1)读取，但树发生结构或键值修改后缓存必须失效。作者方案适合临时查询且树只读；缓存适合稳定快照上的高频查询；带子树大小的平衡树适合查询与更新都频繁的长期结构。三者返回语义相同，生命周期与维护成本不同。

递归期间也要求树不被并发修改。若另一线程改变左右指针，共享计数器看到的访问序列可能既不是修改前也不是修改后的有效中序结果。工程接口应使用不可变快照、读锁或明确的单线程所有权；const指针只禁止当前函数写节点，并不能自动阻止其他执行路径修改同一棵树。

迭代中序可以显式维护栈，避免程序调用栈，但辅助空间仍为O(h)。

#include <stack>
 
const BinaryTreeNode* KthNodeIterative(
    const BinaryTreeNode* root,
    unsigned int k) {
    if (root == nullptr || k == 0) {
        return nullptr;
    }
 
    std::stack<const BinaryTreeNode*> path;
    const BinaryTreeNode* current = root;
    while (current != nullptr ||
           !path.empty()) {
        while (current != nullptr) {
            path.push(current);
            current = current->m_pLeft;
        }
 
        current = path.top();
        path.pop();
        if (--k == 0) {
            return current;
        }
        current = current->m_pRight;
    }
    return nullptr;
}

迭代版在访问节点时先递减再检查0，与作者“先检查1再递减”等价。k初始为0仍必须在入口拦截，否则unsigned前减会下溢。

重复键与“第k个”的含义

作者测试所有键唯一，BinaryTreeNode也没有记录重复次数。若某个BST实现允许重复键，中序仍可非递减，但必须先决定重复节点放左还是放右。

排名可以按“节点个数”计，也可以按“不同键值”计。作者算法每访问一个节点就减k，属于按节点计数；两个值相同的节点仍占两个排名。若需求按不同值排名，需要在遍历中记住前一键并跳过重复，或改变数据结构。

因此“BST中序有序”足以支持按节点排名，却不能替调用方决定重复语义。页面和接口应把这一点写清，不能默认所有BST库都采用同样规则。

作者5组树形与28个断言

作者main依次调用TestA到TestE：

  1. TestA是7节点完整平衡树。k为0和8返回空，k为1到7依次返回5到11，共9个断言。
  2. TestB是5、4、3、2、1构成的纯左链。k为1到5返回1到5，0和6返回空，共7个断言。
  3. TestC是1、2、3、4、5构成的纯右链。k为1到5仍返回1到5，0和6返回空，共7个断言。
  4. TestD只有节点1。k为1返回该节点，0和2返回空，共3个断言。
  5. TestE为空树。k为0和1都返回空，共2个断言。

合计9加7加7加3加2等于28。平衡、左斜、右斜、单节点、空树都覆盖，合法排名的首尾和越界两侧也覆盖。

下面用紧凑断言复现最关键路径。完整移植时应保留作者对每个合法k逐一验证，而不只抽查中间值。

#include <cassert>
 
void testKthNode(
    const BinaryTreeNode* balanced,
    const BinaryTreeNode* leftChain,
    const BinaryTreeNode* rightChain,
    const BinaryTreeNode* single) {
    assert(KthNode(balanced, 0) == nullptr);
    for (unsigned int k = 1;
         k <= 7;
         ++k) {
        const BinaryTreeNode* node =
            KthNode(balanced, k);
        assert(node != nullptr);
        assert(node->m_nValue ==
               static_cast<int>(k) + 4);
    }
    assert(KthNode(balanced, 8) == nullptr);
 
    for (unsigned int k = 1;
         k <= 5;
         ++k) {
        assert(KthNode(leftChain, k)
                   ->m_nValue ==
               static_cast<int>(k));
        assert(KthNode(rightChain, k)
                   ->m_nValue ==
               static_cast<int>(k));
    }
 
    assert(KthNode(single, 1)
               ->m_nValue == 1);
    assert(KthNode(single, 2) == nullptr);
    assert(KthNode(nullptr, 0) == nullptr);
    assert(KthNode(nullptr, 1) == nullptr);
}

随机对拍可先生成一组唯一整数，随机打乱插入BST，再把原值排序成参考序列。对每个合法k，作者函数返回值应等于参考序列下标k减1；对0和节点数加1应返回空。这样能同时检验树形变化和排名方向。

还可给节点访问函数加计数，断言k等于1时不访问整棵树，从而验证提前终止真实发生，而不是仅在结果上碰巧正确。

本章练习

练习

问题 1： 为什么中序遍历能得到升序序列？

问题 2： k 为什么必须按引用传递？

问题 3： 题面"第 k 大"与源码"第 k 小"如何区分？

概念说明

本章核心概念包括：有序节点序列。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

  1. 二叉搜索树中序遍历形成有序节点序列，可直接按访问次数排名。
  2. k通过引用成为共享计数器，访问当前节点时从1开始判断。
  3. target非空后停止当前节点和右子树处理，实现提前终止。
  4. 作者题面写第k大，但源码和28个断言实际返回第k小。
  5. 真正第k大使用右、根、左；不能只改函数名。
  6. k等于0、空树或k超过节点数都返回nullptr。
  7. 时间为O(h加k)、栈空间O(h)，斜树最坏达到O(n)。
  8. 旧页把answer为空写成退出条件，会在第一次调用就错误返回。

名词解释

名词解释

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

中序遍历
左-根-右的遍历次序，对 BST 输出升序序列。
节点排名
中序序列中的位置序号，第 k 个即第 k 小。
引用传递
计数变量跨递归共享，而非各分支副本。
复习本章（5 题）

讨论

评论区加载中…