117. Populating Next Pointers in Each Node II

Question

Given a binary tree

1
2
3
4
5
6
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

Populate each next pointer to point to its next right node. If > there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Solution

BFS搜索,从右至左将每层节点放入队列。
用一个size记录该层级放入节点的数量,每次循环将size-1,当size归零时放入新一层级的节点。

Code

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
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;

public Node() {}

public Node(int _val) {
val = _val;
}

public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/

class Solution {
public Node connect(Node root) {
if(root == null) return root;

Queue<Node> q = new LinkedList();
q.add(root);

while(!q.isEmpty()){
int size = q.size();
Node next = null;
while(size > 0){
size--;
Node curr = q.poll();
curr.next = next;
next = curr;
if(curr.right != null) q.add(curr.right);
if(curr.left != null) q.add(curr.left);
}
}
return root;
}
}
Author

Xander

Posted on

2022-04-21

Updated on

2022-05-12

Licensed under

Comments