面试题55（一）：二叉树的深度

从“1到7这条路径有多长”开始

先预测：作者Test1中根1的左孩子是2，右孩子是3；2连接4和5，5再连接7；3连接右孩子6。最长根到叶路径是1、2、5、7。

题目把从根到依次经过的节点组成一条路径，并把最长路径上的节点数量定义为二叉树的深度。因此这条路径深度为4，不是3。

这种以节点数为单位的约定称为。若另一套接口按边数定义高度，同一条路径会记为3；两种约定都可用，但不能在基例和测试中混用。

从根问题拆成两个子问题

非空树的最长路径必定从根开始，然后进入左子树或右子树，不能同时走两侧。于是先求左右两个，再选更大的结果并为当前根加1。

这正是作者概念“左右子树深度的较大值加1”。空指针没有节点，深度为0；非空节点的结果是max(leftDepth, rightDepth)加1。

若两个子树同深，选哪一侧都得到相同数值。若只需要深度，不需要返回具体路径，就无需记录父指针或节点列表。

图中叶节点4、7、6都从两个空子树得到0并返回1；节点5返回2，节点2返回3，节点3返回2，根1最终返回4。

忠实还原作者递归

作者函数只接收const根指针，没有全局状态，也不会修改树。

int TreeDepth(
    const BinaryTreeNode* pRoot) {
    if (pRoot == nullptr) {
        return 0;
    }
 
    int nLeft =
        TreeDepth(pRoot->m_pLeft);
    int nRight =
        TreeDepth(pRoot->m_pRight);
 
    return (nLeft > nRight)
        ? (nLeft + 1)
        : (nRight + 1);
}

源码先完整计算左深度，再计算右深度，最后取较大值。这种先取得孩子结果、再计算父结果的模式称为。它与“用一个全局最大值在遍历时更新”是不同实现。

旧页写“递归返回后更新全局最大值”，但作者没有全局变量。局部返回值让函数可重入：两个调用各自只依赖参数和子调用结果，不会共享一份容易忘记清零的历史状态。

正确性可用结构归纳说明。空树返回0，与定义一致；假设左右子树函数都返回真实深度，任何根到叶路径只能经过其中一棵子树，最长者就是两者较大值，再加当前根节点1。因此当前树也返回真实深度。

节点数与边数不要差一

按节点数定义时，空树0、叶节点1、根加一层。按边数定义时，常把空树记为-1、叶节点记为0，或者额外约定空树0。若调用方只说“高度”，应先确认单位，再写基例。

作者返回int。深度不会超过节点数，但极端树若节点数超过int上限，返回值也无法表示；更早出现的现实风险通常是递归栈耗尽。

只返回一个整数时，父节点无需知道最深路径经过了哪些具体节点。若产品还要展示路径，可以让递归同时返回深度和路径，父节点选择更深一侧后把当前节点放到路径前端；但每层复制vector会把斜树成本放大到O(n平方)。更稳妥的做法是第一次只求左右深度并记录每个节点选中的孩子，第二次从根沿选择指针走到叶；或返回目标叶指针，再通过父指针逆向恢复。左右同深时还要规定稳定选择左侧、右侧或字典序较小路径，否则测试结果可能随实现细节变化。

树深也不同于二叉树直径。深度路径必须从当前根出发，只能选择左或右一侧，所以递推取较大值；直径允许从某个左侧叶子经过祖先走到右侧叶子，候选长度才会组合左右两侧。把nLeft与nRight相加再加1写进TreeDepth，得到的是“经过当前节点的最长叶间路径候选”，既不是当前子树深度，也还不是全树直径，因为全树直径还需和两个子树内部直径比较。

时间看节点，空间看树高

每个非空节点被调用一次，每个空子指针也只触发常数工作，所以时间复杂度O(n)。算法不能因为某一侧已经很深就跳过另一侧，因为未检查的一侧可能更深。

空间不是O(1)。未返回的函数调用保存在中，峰值等于树高h，因此辅助空间O(h)。

平衡树的h约为O(log n)，纯左链或纯右链的h等于n。作者Test2和Test3都构造5节点单链，验证左右方向对称；生产中若树可能有数十万层，递归版可能在得出答案前栈溢出。

const只限制当前函数通过该指针修改节点，不保证其他线程不会并发改树。计算期间结构应保持稳定，否则一次遍历可能看到不一致的左右关系。

如果同一棵不可变树会被频繁询问深度，可以在节点或树对象中缓存计算结果，使后续查询O(1)。缓存把一次O(n)遍历换成持久空间，前提是树结构确实不会变化；插入、删除或替换任意子树后，修改路径上所有祖先的缓存都要失效。可变树若只更新一条根到叶路径，可沿父指针自底向上重算到结果不再变化；没有父指针或修改批量很大时，重新全树计算往往更简单可靠。

并发环境下，缓存还要解决发布与一致性。两个线程同时首次计算虽通常得到同一数值，但无同步写共享字段仍是数据竞争；加锁、一次初始化或不可变快照都可以建立清晰边界。作者的纯函数版本不保存结果，牺牲重复查询速度，却天然避免缓存失效和共享写状态。

层序遍历按层计数

广度优先搜索可以用队列逐层处理。每完成队列当前层的全部节点，depth加1；空树仍返回0。

#include <queue>
 
int TreeDepthByLevel(
    const BinaryTreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
 
    std::queue<const BinaryTreeNode*> nodes;
    nodes.push(root);
    int depth = 0;
 
    while (!nodes.empty()) {
        const std::size_t levelSize =
            nodes.size();
        for (std::size_t i = 0;
             i < levelSize;
             ++i) {
            const BinaryTreeNode* node =
                nodes.front();
            nodes.pop();
            if (node->m_pLeft != nullptr) {
                nodes.push(node->m_pLeft);
            }
            if (node->m_pRight != nullptr) {
                nodes.push(node->m_pRight);
            }
        }
        ++depth;
    }
    return depth;
}

该版本时间仍为O(n)。队列峰值是某一层的最大宽度w，空间O(w)；完全二叉树的最后一层可接近n的一半。它避免调用栈过深，但不一定比递归更省内存。

如果业务还需要每层节点、最大宽度或层序序列，BFS可顺便产生这些数据；只求深度且树高受控时，作者递归更直接。

显式栈保存节点与层数

深度优先也能改为迭代。栈中同时保存节点和该节点所在层，弹出时更新当前最大层。

#include <algorithm>
#include <stack>
#include <utility>
 
int TreeDepthIterative(
    const BinaryTreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
 
    std::stack<
        std::pair<
            const BinaryTreeNode*, int>> pending;
    pending.push({root, 1});
    int answer = 0;
 
    while (!pending.empty()) {
        const auto [node, depth] =
            pending.top();
        pending.pop();
        answer = std::max(answer, depth);
 
        if (node->m_pLeft != nullptr) {
            pending.push(
                {node->m_pLeft, depth + 1});
        }
        if (node->m_pRight != nullptr) {
            pending.push(
                {node->m_pRight, depth + 1});
        }
    }
    return answer;
}

显式栈把内存放到堆管理容器中，避免受限的程序调用栈，但最坏仍需O(h)或更多待处理节点。它还便于加入深度上限：若depth超过安全阈值可提前报告，而不是继续递归直到崩溃。

深度上限不应伪装成真实答案。若接口因安全策略最多接受10000层，超出时应返回错误状态或抛出约定异常，而不是静默返回10000；否则调用方无法区分“深度恰好达到上限”和“结果被截断”。同样，遍历被取消或内存分配失败也应与正常整数深度分开表达。作者示例面向内存中的可信小树，因此直接返回int；服务边界上的实现需要额外的资源预算与错误通道。

输入必须是真正的树

作者假设左右指针形成有限、无环、每个节点只有一个父路径的二叉树。若某个孩子指回祖先，递归不会到达空指针，BFS和显式栈也会无限重复。

若两个父节点共享同一子树，结构是有向无环图而不是树。作者函数仍可能终止，但会重复计算共享部分；“根到叶最长路径”仍可定义，却不再是标准树的复杂度模型。对未知图结构应维护访问状态并使用图算法。

作者5组测试逐项还原

1. Test1是7节点普通分叉树，最长路径1、2、5、7，期望4。
2. Test2是1到5的纯左链，期望5。
3. Test3是1到5的纯右链，期望5。
4. Test4只有根节点1，期望1。
5. Test5传入nullptr，空树深度为0。

这5组同时覆盖左右不等深、两个极端方向、最小非空树和空树。作者没有单独测试完美平衡树，但Test1已经包含左右分支并要求选择更深一侧。

#include <cassert>
 
void testTreeDepth(
    const BinaryTreeNode* ordinary,
    const BinaryTreeNode* leftChain,
    const BinaryTreeNode* rightChain,
    const BinaryTreeNode* single) {
    assert(TreeDepth(ordinary) == 4);
    assert(TreeDepth(leftChain) == 5);
    assert(TreeDepth(rightChain) == 5);
    assert(TreeDepth(single) == 1);
    assert(TreeDepth(nullptr) == 0);
 
    assert(TreeDepth(ordinary) ==
           TreeDepthByLevel(ordinary));
    assert(TreeDepth(ordinary) ==
           TreeDepthIterative(ordinary));
}

随机对拍可按概率生成有限树，同时用递归、BFS和显式栈求深度，三者应一致。生成器必须设最大层数或节点预算，避免测试数据自身无限扩张。

还可做结构性质测试：给任意树外包一层新根并把原树放在一侧，新树深度应等于原深度加1；左右子树互换不应改变深度。

另一组性质来自单调性：在任意叶节点下新增一个孩子，深度只可能保持不变或增加1，绝不减少；若该叶本就在某条最长路径上，结果必须增加1。删除一棵非最长分支不应改变结果，删除所有最长分支之一则要看是否还有同深替代路径。这些性质比固定示例更容易捕获错误地取较小值、错误地相加或遗漏某侧递归。

本章练习

概念说明

本章核心概念包括：空树深度为0。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

1. 二叉树的深度是根到叶最长路径上的节点数。
2. 空树深度为0，单节点树深度为1，明确了节点计数基例。
3. 非空树返回左右子树深度的较大值加1。
4. 作者使用局部递归返回值，没有全局最大值。
5. 递归通过后序汇总自底向上组合，正确性可用结构归纳证明。
6. 时间O(n)，递归栈O(h)；斜树可能导致栈溢出。
7. BFS按层计数，显式DFS保存节点层数，均可避免函数递归。
8. 作者5组测试覆盖普通树、左右单链、单节点和空树。

名词解释