[AcWing]71. 二叉树的深度

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

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

数据范围

树中节点数量 [0,500]

样例

1
2
3
4
5
6
7
8
输入:二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示:
8
/ \
12 2
/ \
6 4

输出:3

算法思想

对二叉树进行DFS遍历,在这个过程中,进入下一子树,则depth + 1
取左右子树depth的最大值。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 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 dfs(TreeNode * root, int depth){
// 如果遍历到了树底,返回深度
if(!root) return depth;
// 有左子树就遍历左子树,有右子树就遍历右子树
// 取两个子树的最大深度
return max(dfs(root -> left, depth + 1), dfs(root -> right, depth + 1));
}

int treeDepth(TreeNode* root) {
return dfs(root, 0);
}
};

时间复杂度

DFS遍历,每个节点只被遍历一次,时间复杂度是O(n)