forked from yangyiRunning/DataStructureAlgorithmsJava
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMaxDepth.java
More file actions
113 lines (104 loc) · 2.99 KB
/
MaxDepth.java
File metadata and controls
113 lines (104 loc) · 2.99 KB
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
package ds;
import java.util.ArrayDeque;
import java.util.Queue;
/**
* 给定一个二叉树，找出其最大深度。
* <p>
* 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
* <p>
* 说明: 叶子节点是指没有子节点的节点。
* <p>
* 示例：
* 给定二叉树 [3,9,20,null,null,15,7]，
* <p>
* 3
* / \
* 9 20
* / \
* 15 7
* 返回它的最大深度 3 。
*
* @author yangyi 2019年01月28日21:12:36
*/
public class MaxDepth {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
}
/**
* 广度优先搜索的层级遍历
* <p>
* 关键奥义为记录两层的节点个数
*/
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
//当前层的节点个数
int currentLevelCount = 1;
//下一层的节点个数
int nextCurrentLevelCount = 0;
//广度优先遍历到哪一层了
int level = 0;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
currentLevelCount--;
if (node.left != null) {
queue.offer(node.left);
nextCurrentLevelCount++;
}
if (node.right != null) {
queue.offer(node.right);
nextCurrentLevelCount++;
}
if (currentLevelCount == 0) {
currentLevelCount = nextCurrentLevelCount;
nextCurrentLevelCount = 0;
level++;
}
}
return level;
}
/**
* 深度优先搜索的"一根筋"似的检测
*/
public int maxDepthRecursion(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null) {
return maxDepthRecursion(root.right) + 1;
}
if (root.right == null) {
return maxDepthRecursion(root.left) + 1;
}
return Math.max(maxDepthRecursion(root.left), maxDepthRecursion(root.right)) + 1;
}
public TreeNode createTree() {
TreeNode node_3 = new TreeNode();
node_3.val = 3;
TreeNode node_9 = new TreeNode();
node_9.val = 9;
TreeNode node_20 = new TreeNode();
node_20.val = 20;
TreeNode node_15 = new TreeNode();
node_15.val = 15;
TreeNode node_7 = new TreeNode();
node_7.val = 7;
node_3.left = node_9;
node_3.right = node_20;
node_9.left = node_15;
node_20.right = node_7;
return node_3;
}
public static void main(String[] args) {
MaxDepth maxDepth = new MaxDepth();
int level = maxDepth.maxDepth(maxDepth.createTree());
System.out.println("最大层级数为:" + level);
int level2 = maxDepth.maxDepthRecursion(maxDepth.createTree());
System.out.println("最大层级数为:" + level2);
}
}