forked from pxu/Algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPopulatingNextRightPointers.java
More file actions
39 lines (34 loc) · 1.11 KB
/
PopulatingNextRightPointers.java
File metadata and controls
39 lines (34 loc) · 1.11 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
public class PopulatingNextRightPointers {
public void connect(TreeLinkNode root) {
if(root == null) return;
root.next = null;
while(root != null) {
TreeLinkNode first = root;
TreeLinkNode p = first;
while(p != null) {
if(p.left != null) {
if(p.right != null) p.left.next = p.right;
else p.left.next = findNephew(p.next);
}
if(p.right != null) {
p.right.next = findNephew(p.next);
}
p = p.next;
}
if(first.left != null) root = first.left;
else if(first.right != null) root = first.right;
else {
root = findNephew(root.next);
}
}
}
public TreeLinkNode findNephew(TreeLinkNode node) {
if(node == null) return null;
while(node != null) {
if(node.left != null) return node.left;
else if(node.right != null) return node.right;
else node = node.next;
}
return null;
}
}