递归与迭代：计算二叉树深度的方法

"本文将介绍如何通过递归和迭代两种方式计算二叉树的深度，以C++语言为例提供示例代码。" 在计算机科学中，二叉树是一种常见的数据结构，它的每个节点最多有两个子节点，通常分为左子节点和右子节点。计算二叉树的深度是理解和操作二叉树时的重要任务，因为深度决定了树的层次结构。二叉树的深度是指从根节点到最远叶子节点的最长路径上边的数目。 ### 递归方法 递归方法基于二叉树的分治性质，即每个节点的深度是其左右子树深度中的最大值加上1。以下是一个使用C++实现的递归函数`maxDepth`： ```cpp int maxDepth(TreeNode* root) { if (root == nullptr) { return 0; } else { int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); return std::max(leftDepth, rightDepth) + 1; } } ``` 在此函数中，如果节点为空，返回0表示没有深度。否则，计算左子树和右子树的深度，并返回较大的那个值加1，这表示当前节点所在的层级。 ### 迭代方法 迭代方法通常使用广度优先搜索（BFS）策略，通过队列来逐层遍历二叉树。以下是一个使用C++实现的迭代版本的`maxDepth`函数： ```cpp int maxDepth(TreeNode* root) { if (root == nullptr) { return 0; } queue<TreeNode*> q; q.push(root); int depth = 1; // 根节点所在层级为1 while (!q.empty()) { 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); } } depth++; // 进入下一层，深度加1 } return depth; } ``` 在这个函数中，我们首先检查根节点是否为空。如果不为空，我们将根节点放入队列，并初始化深度为1。然后，我们在每一层遍历所有节点，将其子节点加入队列。每完成一层的遍历，我们就将深度增加1，直到队列为空，表示所有节点都已处理。 ### 总结 计算二叉树的深度是二叉树操作的基础，递归和迭代是两种常用的实现方法。递归方法简洁直观，但可能会导致大量的函数调用，占用更多的栈空间。而迭代方法虽然代码稍微复杂，但空间效率更高，尤其对于深且宽的二叉树更为适用。根据具体应用场景和性能需求，可以选择合适的方法。