二叉树的深度

---

输入一棵二叉树的根结点，求该树的深度。

从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

数据范围

树中节点数量 $[0,500]$。

样例

输入：二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示：8/ \12  2/ \6   4输出：3

---

算法思路

该算法使用递归的方式计算二叉树的最大深度。对于每个节点，其深度等于其左右子树深度的最大值加1。递归的终止条件是遇到空节点，此时深度为0。

• 时间复杂度：O(n)，其中n是二叉树的节点数。因为需要访问每个节点一次。
• 空间复杂度：O(h)，其中h是二叉树的高度。递归栈的深度取决于树的高度，最坏情况下（树退化为链表）为O(n)，平均情况下（平衡二叉树）为O(log n)。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int treeDepth(TreeNode* root) {// 递归终止条件：当前节点为空，深度为0if(!root) return 0;// 递归计算左右子树的深度，取最大值加1作为当前节点的深度return max(treeDepth(root->left), treeDepth(root->right)) + 1;}
};

示例演示

示例1：平衡二叉树

输入:3/ \9  20/  \15   7执行过程:
1. treeDepth(3)- treeDepth(9) → 1- treeDepth(20)- treeDepth(15) → 1- treeDepth(7) → 1- max(1, 1) + 1 = 2- max(1, 2) + 1 = 3输出: 3

示例2：左斜树

输入:1/2/3执行过程:
1. treeDepth(1)- treeDepth(2)- treeDepth(3) → 1- treeDepth(NULL) → 0- max(1, 0) + 1 = 2- treeDepth(NULL) → 0- max(2, 0) + 1 = 3输出: 3

示例3：空树

输入: NULL执行过程:
直接返回0输出: 0

---

扩展

优化1：迭代实现（BFS）

使用广度优先搜索（BFS）来计算树的深度，避免递归栈的开销。

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

特点：

• 空间复杂度：O(n)，最坏情况下队列中存储所有叶子节点
• 适合深度较大的树，避免递归栈溢出

优化2：迭代实现（DFS）

使用深度优先搜索（DFS）的迭代版本，模拟递归过程。

int treeDepth(TreeNode* root) {if (!root) return 0;stack<pair<TreeNode*, int>> st;st.push({root, 1});int maxDepth = 0;while (!st.empty()) {auto [node, depth] = st.top();st.pop();maxDepth = max(maxDepth, depth);if (node->right) st.push({node->right, depth + 1});if (node->left) st.push({node->left, depth + 1});}return maxDepth;
}

特点：

• 空间复杂度：O(h)，h为树高
• 更接近递归的思路，但使用显式栈

方法	时间复杂度	空间复杂度	适用场景
原始递归	O(n)	O(h)	代码简洁，容易理解
BFS迭代	O(n)	O(n)	适合广度较大的树
DFS迭代	O(n)	O(h)	更接近递归的思路

1. 递归方法：代码简洁，适合大多数场景，但需要注意递归深度限制
2. BFS迭代：适合需要层次遍历信息的场景，或担心递归栈溢出时
3. DFS迭代：适合需要模拟递归过程的场景，空间效率优于BFS