层序遍历
# 102. 二叉树的层序遍历 (opens new window)
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
Queue<TreeNode> que = new LinkedList<>();
if(root==null)
return ret;
que.offer(root);
while(!que.isEmpty()){
List<Integer> level = new ArrayList<>();
int size = que.size();
while(size>0){
TreeNode node = que.poll();
level.add(node.val);
if(node.left!=null)
que.offer(node.left);
if(node.right!=null)
que.offer(node.right);
size--;
}
ret.add(level);
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 199. 二叉树的右视图 (opens new window)
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if(root==null)
return ret;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
int size = que.size();
while(size>0){
TreeNode node = que.poll();
if(size==1)
ret.add(node.val);
if(node.left!=null)
que.add(node.left);
if(node.right!=null)
que.add(node.right);
size--;
}
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 107. 二叉树的层序遍历 II (opens new window)
# 103. 二叉树的锯齿形层序遍历 (opens new window)
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
Queue<TreeNode> que = new LinkedList<>();
if(root!=null)
que.add(root);
while(!que.isEmpty()){
LinkedList<Integer> level = new LinkedList<>();
int size = que.size();
while(size>0){
TreeNode cur = que.poll();
if(ret.size()%2==0)
level.addLast(cur.val);
else
level.addFirst(cur.val);
if(cur.left!=null)
que.add(cur.left);
if(cur.right!=null)
que.add(cur.right);
size--;
}
ret.add(level);
}
return ret;
}
}
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
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
# 429. N 叉树的层序遍历 (opens new window)
# 559. N 叉树的最大深度 (opens new window)
# 662. 二叉树最大宽度 (opens new window)
# 671. 二叉树中第二小的节点 (opens new window)
# 513. 找树左下角的值 (opens new window)
# 515. 在每个树行中找最大值 (opens new window)
# 637. 二叉树的层平均值 (opens new window)
# 623. 在二叉树中增加一行 (opens new window)
# 690. 员工的重要性 (opens new window)
# 958. 二叉树的完全性检验 (opens new window)
遍历到非空节点之前遍历过空节点，返回false；
class Solution {
public boolean isCompleteTree(TreeNode root) {
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
boolean flag = true;
while(!que.isEmpty()){
TreeNode node = que.poll();
if(node == null){
flag = false;
}else{
if(!flag)
return false;
que.add(node.left);
que.add(node.right);
}
}
return true;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19