二叉树的最大深度
难度：简单
描述：
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
思路分析：
实现方法一：递归
利用递归实现深度优先搜索
实现方式二：利用队列
利用队列实现广度优先搜索
代码实现：
var maxDepth = function (root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};
var maxDepth = function (root) {
if (root === null) return 0;
var queue = [root];
var deep = 0;
while (queue.length > 0) {
deep++;
var temp = queue.length;
while (temp > 0) {
var curr = queue.shift();
if (curr.left !== null) {
queue.push(curr.left);
}
if (curr.right !== null) {
queue.push(curr.right);
}
temp--;
}
}
return deep;
};
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var root = new TreeNode(5);
var node1 = new TreeNode(4);
var node2 = new TreeNode(8);
var node3 = new TreeNode(11);
var node4 = new TreeNode(13);
var node5 = new TreeNode(4);
var node6 = new TreeNode(7);
var node7 = new TreeNode(2);
var node8 = new TreeNode(1);
var node9 = new TreeNode(10);
root.left = node1;
root.right = node2;
node1.left = node3;
node2.left = node4;
node2.right = node5;
node3.left = node6;
node3.right = node7;
node5.right = node8;
node6.right = node9;
console.log(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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49