二叉树的最大深度

题意

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的距离。

样例

给出一棵如下的二叉树:

  1
 / \ 
2   3
   / \
  4   5

这个二叉树的最大深度为 3.

思路

递归法

用递归分别遍历每个节点 ,返回相对于当前节点的最大深度(记得加上根节点)。

循环法

非递归写法可以用一个队列来存储,先将根节点存入,并记录当前节点的兄弟节点个数(指来自同一个父节点),当兄弟节点都出队列完毕,就对子节点进行与根节点同样的操作。

代码实现

递归法

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
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: An integer.
*/
public int maxDepth(TreeNode root) {
if (root == null)
return 0;

int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}

//简化写法的话,其实可以一行代码解决:
// return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

循环法

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
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: An integer.
*/
public int maxDepth(TreeNode root) {
if (root == null)
return 0;

Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int depth = 0; //表示二叉树的深度
int count = 0; //表示已从队列中取出当前层的个数
int amount = 1; //表示当前节点的兄弟节点个数

while (queue.size() != 0) {
TreeNode top = queue.poll();
count++;
if (top.left != null) {
queue.add(top.left);
}

if (top.right != null) {
queue.add(top.right);
}

if (count == amount) {
amount = queue.size();
count = 0;
depth++;
}
}
return depth;
}
}

原题地址

LintCode:二叉树的最大深度