-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathpopulatingnode117.java
More file actions
63 lines (57 loc) · 1.92 KB
/
Copy pathpopulatingnode117.java
File metadata and controls
63 lines (57 loc) · 1.92 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
import utils.Node;
import java.util.LinkedList;
import java.util.Queue;
public class populatingnode117 {
//Bfs广度优先算法
public Node connect(Node root) {
if(root==null) return null;
Queue<Node> queue =new LinkedList<Node>();
queue.offer(root);
while(!queue.isEmpty()){
int n=queue.size();
Node last=null;
for(int i=1;i<=n;i++){//遍历当前层的节点
Node cur=queue.poll();
//把当前节点的左右子节点存入队列，如果存在的话
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
if(i!=1){
last.next= cur;
}
last=cur;
}
}
return root;
}
public Node connect2(Node root) {
if(root==null) return root;
//当作每一层的链表
Node cur=root;
while(cur!=null){
//遍历当前层的时候，为了方便操作在下一层前面添加一个哑结点（注意这里是访问当前层的节点，然后把下一层的节点串起来）
Node dump=new Node(0);
Node pre=dump;
//开始遍历当前层的链表
while(cur!=null){
if(cur.left!=null){
pre.next=cur.left;
pre=pre.next;
}
if(cur.right!=null){
pre.next=cur.right;
pre=pre.next;
}
//继续访问这一行的下一个节点
cur=cur.next;
}
//把下一层串联成一个链表之后，让他赋值给cur，
//后续继续循环，直到cur为空为止
cur = dump.next;
}
return root;
}
}