c++中如何计算二叉树的深度_c++求二叉树高度_技术教程

二叉树高度按节点数定义，递归解法为：空节点返回0，否则返回左右子树最大高度加1；非递归用BFS按层计数；注意避免重复计算、段错误及定义混淆。

用递归求二叉树高度，核心就是左右子树最大深度加1

二叉树的高度（深度）定义为从根节点到最远叶子节点的最长路径上的边数或节点数，C++ 中通常按「节点数」算（即空树高度为 0，单节点树高度为 1）。递归是最自然的解法：当前节点高度 = max(左子树高度, 右子树高度) + 1。

关键点在于边界处理：遇到空指针 nullptr 就返回 0。不要写成返回 -1 或 1，否则结果会偏移。

如果按「边数」定义（LeetCode 一些题），空树为 0，单节点为 0，那递归式仍是 max(left, right) + 1，但初始调用后要减 1 —— 更推荐统一用「节点数」定义，避免混淆
函数签名建议用 int getHeight(TreeNode* root)，明确语义；别用 depth 当函数名，容易和「当前递归深度」参数混淆
不推荐在递归中传入引用计数器或全局变量，既难调试又破坏纯函数性

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

非递归写法：用 BFS 层序遍历统计层数

想避免递归栈溢出（比如极不平衡的链状树），就用队列做层序遍历。每处理完一层，高度加 1。比 DFS 递归略慢但空间可控——最坏空间复杂度是 O(w)，其中 w 是最大层宽，而非树高。

注意别把「每 pop 一个节点就 height++」，那是错的；必须按层隔离，用内层循环或记录当前层节点数。

立即学习“C++免费学习笔记（深入）”；

初始化队列后，先检查 if (!root) return 0
每次外层 while 循环开始前，height++；内层 for 循环负责清空当前层所有节点
C++ 中推荐用 queue，别存整数值或智能指针，除非有特殊生命周期管理需求

int getHeightBFS(TreeNode* root) {
    if (!root) return 0;
    std::queue q;
    q.push(root);
    int height = 0;
    while (!q.empty()) {
        height++;
        int levelSize = q.size();
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front(); q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return height;
}

常见错误：把深度和直径、平衡判断混在一起

看到「深度」就下意识套用上面任一函数，但实际场景常有隐藏要求。比如：

isBalanced() 需要同时获取左右子树高度并比较差值，若重复调用 getHeight() 会退化成 O(n²)；应改用后序遍历一次返回高度+是否平衡
求「二叉树直径」本质是找某节点左右子树深度之和的最大值，不能只算根节点的左右高度
某些 OJ 题（如 LeetCode 104）输入可能为空指针，而你的 TreeNode 定义没给默认构造，直接访问 root->left 会段错误

模板类或泛型树时，高度计算逻辑不变但类型要适配

如果你用的是自定义模板节点（如 template struct TreeNode），只要成员名一致（left/right），上面两个函数几乎不用改。但要注意：

模板函数需声明为 template int getHeight(TreeNode* root)，不能漏掉 typename T
若节点存储智能指针（如 std::unique_ptr>），则判空用 !root 仍有效，但访问子节点要写 root->left.get() 或直接用 -> 操作符（unique_ptr 重载了它）
静态断言可加： static_assert(std::is_pointer_vleft)>, "left must be pointer");，提前暴露接口不匹配问题