C++如何计算二叉树的最大深度和最小深度-C++-PHP中文网

最大深度递归需判空节点返回0，非空则取左右子树最大值加1；最小深度递归需避免空子树干扰，用int_max代替，或改用bfs层序遍历直接在首次遇叶子时返回深度。

c++如何计算二叉树的最大深度和最小深度

用递归算最大深度，别漏掉空节点的边界处理

最大深度本质是根到最远叶子节点的边数（或节点数，看题目定义），递归写法最直观。关键点在于：空节点深度为 0，非空节点深度为左右子树深度的最大值加 1。

容易踩的坑：nullptr 没判直接访问 left/right 会崩溃；有人误把“空节点返回 -1”再加 1，逻辑绕且易错。

标准定义下，空树深度为 0，单节点树深度为 1
递归终止条件必须是 root == nullptr，返回 0
不要在递归前做 if (root->left == nullptr && root->right == nullptr) 特判叶子——这不简化逻辑，反而增加分支

int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    return std::max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

最小深度不是“左右子树最小值加 1”，要区分单子树情况

最小深度是根到最近叶子节点的节点数（或边数）。陷阱在于：如果某节点只有左子树，它的最小深度不能只看左子树——因为右子树为空，不能算作一条有效路径。必须确保目标节点是叶子（left == nullptr && right == nullptr）。

常见错误现象：minDepth(root->left) 和 minDepth(root->right) 直接取 std::min，导致空子树返回 0，结果变成 0 + 1 = 1，误判成深度 1。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

遇到空节点，返回一个极大值（如 INT_MAX），避免干扰 std::min
遇到叶子节点，立即返回 1
若左/右子树之一为空，只递归非空侧

int minDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;
    int left = (root->left) ? minDepth(root->left) : INT_MAX;
    int right = (root->right) ? minDepth(root->right) : INT_MAX;
    return std::min(left, right) + 1;
}

BFS 层序遍历求最小深度更直观，适合避免递归栈溢出

最小深度天然适合 BFS：第一次遇到叶子节点时的层数就是答案。相比 DFS 递归，BFS 不需要回溯、无栈溢出风险，且提前终止效率高。

使用场景：树可能极不平衡（比如退化成链表），递归深度接近 10⁵ 级别时，BFS 更稳妥。

用 queue<treenode></treenode> 存节点，另用变量记录当前层节点数
每处理完一层，深度 +1；一旦发现某个节点的 left 和 right 都为 nullptr，立刻返回当前深度
不需要额外空间存整棵树结构，空间复杂度是单层最宽宽度

int minDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    queue<treenode> q;
    q.push(root);
    int depth = 1;
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i left == nullptr && node->right == nullptr) return depth;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        ++depth;
    }
    return depth;
}</treenode>

LeetCode 题号和定义差异必须核对清楚

不同平台对“深度”的定义可能不同：LeetCode 104. Maximum Depth of Binary Tree 和 111. Minimum Depth of Binary Tree 都以节点数计（空树为 0，单节点为 1）；但有些题或教材按边数计（单节点为 0）。不看清题干直接套模板，可能全错。