# 面试题55 - I. 二叉树的深度
# 示例
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# JS
1.递归思路
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function (root) {
const treeDep = function (node, n = 0) {
if (node) {
let l = treeDep(node.left, n + 1)
let r = treeDep(node.right, n + 1)
return l > r ? l : r;
}
return n
}
return treeDep(root)
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2.非递归思路 使用层序遍历(BFS)
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function (root) {
const treeDep = function (node) {
let level = 0
let queue = []
if (!node) {
return level
}
queue.push(node)
while (queue.length !== 0) {
let len = queue.length
level++
while (len) {
let n = queue.shift()
if (n.left) {
queue.push(n.left)
}
if (n.right) {
queue.push(n.right)
}
len--
}
}
return level
}
return treeDep(root)
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30