Skip to content

Commit b8d323d

Browse files
idfidf
committed
Populating Next Right Pointers in Each Node
1 parent 527344d commit b8d323d

3 files changed

Lines changed: 181 additions & 0 deletions

File tree

‎src/PopulatingNextRightPointersinEachNode/Solution.java‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
package PopulatingNextRightPointersinEachNode;
2+
3+
import commons.datastructures.TreeLinkNode;
4+
5+
/**
6+
* User: Danyang
7+
* Date: 1/27/2015
8+
* Time: 21:49
9+
*
10+
* Given a binary tree
11+
12+
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be
13+
set to NULL.
14+
15+
Initially, all next pointers are set to NULL.
16+
17+
Note:
18+
19+
You may only use constant extra space.
20+
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two
21+
children).
22+
For example,
23+
Given the following perfect binary tree,
24+
1
25+
/ \
26+
2 3
27+
/ \ / \
28+
4 5 6 7
29+
After calling your function, the tree should look like:
30+
1 -> NULL
31+
/ \
32+
2 -> 3 -> NULL
33+
/ \ / \
34+
4->5->6->7 -> NULL
35+
*/
36+
public class Solution {
37+
/**
38+
* bfs is trivial
39+
* but require constant space thus can only dfs
40+
*
41+
*
42+
* Algorithm:
43+
* Since full binary tree, it relies on parent's next
44+
*
45+
* Notice:
46+
* 1. pre-order recursive traversal can be converted to iterative
47+
* 2. keep as few iterators as possible
48+
* @param root
49+
*/
50+
public void connect_recur(TreeLinkNode root) {
51+
if(root==null)
52+
return;
53+
if(root.left!=null)
54+
root.left.next = root.right;
55+
if(root.right!=null && root.next!=null)
56+
root.right.next = root.next.left;
57+
connect_recur(root.left);
58+
connect_recur(root.right);
59+
}
60+
61+
public void connect(TreeLinkNode root) {
62+
if(root==null)
63+
return ;
64+
for(TreeLinkNode p=root; p!=null; p=p.left ) { // vertical
65+
for(TreeLinkNode cur=p; cur!=null; cur=cur.next) { // horizontal
66+
if(cur.left!=null)
67+
cur.left.next = cur.right;
68+
if(cur.right!=null && cur.next!=null)
69+
cur.right.next = cur.next.left;
70+
}
71+
}
72+
}
73+
}

‎src/PopulatingNextRightPointersinEachNodeII/Solution.java‎

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
package PopulatingNextRightPointersinEachNodeII;
2+
3+
import commons.datastructures.TreeLinkNode;
4+
5+
/**
6+
* User: Danyang
7+
* Date: 1/27/2015
8+
* Time: 22:51
9+
* Follow up for problem "Populating Next Right Pointers in Each Node".
10+
11+
What if the given tree could be any binary tree? Would your previous solution still work?
12+
13+
Note:
14+
15+
You may only use constant extra space.
16+
For example,
17+
Given the following binary tree,
18+
1
19+
/ \
20+
2 3
21+
/ \ \
22+
4 5 7
23+
After calling your function, the tree should look like:
24+
1 -> NULL
25+
/ \
26+
2 -> 3 -> NULL
27+
/ \ \
28+
4-> 5 -> 7 -> NULL
29+
*/
30+
public class Solution {
31+
/**
32+
* more handling than Populating Next Right Pointers in Each Node
33+
*
34+
* Notice:
35+
* 1. must go to right sub-tree first; consider the example - bottom level only have two nodes: leftmost and rightmost
36+
* 2. recursive solution can be converted to iterative solution
37+
* 3. Is iterative solution not affected by traversing right subtree first as in recursive solution? Need
38+
* modification of the way of going to next level.
39+
* @param root
40+
*/
41+
public void connect_recur(TreeLinkNode root) {
42+
if(root==null)
43+
return;
44+
if(root.left!=null) {
45+
if(root.right!=null)
46+
root.left.next = root.right;
47+
else
48+
root.left.next = getNextParentNextChild(root);
49+
}
50+
if(root.right!=null) {
51+
root.right.next = getNextParentNextChild(root);
52+
}
53+
54+
connect_recur(root.right);
55+
connect_recur(root.left);
56+
}
57+
58+
TreeLinkNode getNextParentNextChild(TreeLinkNode p) {
59+
p = p.next;
60+
while(p!=null) {
61+
if(p.left!=null)
62+
return p.left;
63+
else if(p.right!=null)
64+
return p.right;
65+
p = p.next;
66+
}
67+
return null;
68+
}
69+
70+
public void connect(TreeLinkNode root) {
71+
if(root==null)
72+
return;
73+
for(TreeLinkNode p=root; p!=null; p=nextLevel(p)) {
74+
for(TreeLinkNode c=p; c!=null; c=c.next) {
75+
if(c.left!=null)
76+
if(c.right!=null)
77+
c.left.next = c.right;
78+
else
79+
c.left.next = getNextParentNextChild(c);
80+
if(c.right!=null)
81+
c.right.next = getNextParentNextChild(c);
82+
}
83+
}
84+
}
85+
86+
TreeLinkNode nextLevel(TreeLinkNode p) {
87+
while(p!=null) {
88+
if(p.left!=null)
89+
return p.left;
90+
if(p.right!=null)
91+
return p.right;
92+
p = p.next;
93+
}
94+
return null;
95+
}
96+
}

‎src/commons/datastructures/TreeLinkNode.java‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
package commons.datastructures;
2+
3+
/**
4+
* User: Danyang
5+
* Date: 1/27/2015
6+
* Time: 21:50
7+
*/
8+
public class TreeLinkNode {
9+
public int val;
10+
public TreeLinkNode left, right, next;
11+
public TreeLinkNode(int x) { val = x; }
12+
}

0 commit comments

Comments
 (0)