c++中如何计算二叉树深度_c++二叉树深度计算方法-C++-PHP中文网

c++中如何计算二叉树深度_c++二叉树深度计算方法

穿越時空

发布： 2025-10-04 09:51:02

原创

832人浏览过

二叉树深度计算有递归和非递归两种方法：递归法通过比较左右子树深度取最大值加1，空节点返回0；非递归法使用队列进行层序遍历，每层深度加1。前者代码简洁，后者避免栈溢出，适用于深树场景。

c++中如何计算二叉树深度_c++二叉树深度计算方法

在C++中计算二叉树的深度，通常使用递归方法。二叉树的深度定义为从根节点到最远叶子节点的最长路径上的节点数。空树的深度为0，只有一个根节点的树深度为1。

定义二叉树节点结构

首先需要定义二叉树的节点结构：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

登录后复制

递归计算二叉树深度

通过递归方式，分别计算左子树和右子树的深度，取较大值加1（当前节点）即为整棵树的深度。

int maxDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

登录后复制

非递归方法（使用队列进行层序遍历）

也可以使用广度优先搜索（BFS）的方式，按层遍历树，每处理一层，深度加1。

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

算家云

高效、便捷的人工智能算力服务平台

查看详情

#include <queue>
<p>int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;</p><pre class='brush:php;toolbar:false;'>std::queue<TreeNode*> q;
q.push(root);
int depth = 0;

while (!q.empty()) {
    int levelSize = q.size();
    depth++;
    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 depth;

登录后复制

}

递归方法代码简洁，易于理解；非递归方法避免了递归可能带来的栈溢出问题，适合深度较大的树。选择哪种方式取决于具体应用场景和性能要求。

基本上就这些，不复杂但容易忽略细节，比如空指针判断。

以上就是c++++中如何计算二叉树深度_c++二叉树深度计算方法的详细内容，更多请关注php中文网其它相关文章！