Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
- You may only use constant extra space.
For example,
Given the following binary tree,
Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
http://www.cnblogs.com/springfor/p/3889327.html
这道题跟I的区别就是binary tree不是完全二叉树。
所以root.right.next就不一定等于root.next.left。
所以，目标就是先确定好root的右孩子的第一个有效next连接点，然后再处理左孩子。
Compute right siblings PopulatingNextRightPointers.java
public static class BinaryTreeNode<T> {public T data;
public BinaryTreeNode<T> left, right;
public BinaryTreeNode<T> next; // Populates this field.
public BinaryTreeNode(T data) {
this.data = data;
}
}
public static void populateNextPointer(BinaryTreeNode<Integer> root) {
BinaryTreeNode<Integer> leftStart = root;
while (leftStart != null) {
BinaryTreeNode<Integer> parent = leftStart;
while (parent != null) {
if (parent.left != null) {
parent.left.next = parent.right;
}
if (parent.right != null && parent.next != null) {
parent.right.next = parent.next.left;
}
parent = parent.next;
}
leftStart = leftStart.left;
}
}
terative Version from http://www.darrensunny.me/leetcode-populating-next-right-pointers-in-each-node-ii/
public void connect(TreeLinkNode root) {
if (root == null) // Empty tree
return;
TreeLinkNode headOfNextLevel = root;
// Between levels
while(headOfNextLevel != null) {
// Initialize tailOfNextLevel and current
TreeLinkNode tailOfNextLevel = null, current = headOfNextLevel;
headOfNextLevel = null;
// Within a level
while(current != null) {
// Update headOfNextLevel if we find the first node in the next level
if (headOfNextLevel == null) {
if (current.left != null)
headOfNextLevel = current.left;
else if (current.right != null)
headOfNextLevel = current.right;
}
// Link its two subtrees if both exist
if (current.left != null && current.right != null)
current.left.next = current.right;
if (tailOfNextLevel != null) {
// Link the currently last node in the next level to a subtree (if any) of current node
if (current.left != null && current.right != null) {
tailOfNextLevel.next = current.left;
tailOfNextLevel = current.right;
} else if (current.left != null) {
tailOfNextLevel.next = current.left;
tailOfNextLevel = current.left;
} else if (current.right != null) {
tailOfNextLevel.next = current.right;
tailOfNextLevel = current.right;
}
} else if (headOfNextLevel != null) {
// The first node in the next level has been found
if (headOfNextLevel.next != null)
tailOfNextLevel = headOfNextLevel.next;
else
tailOfNextLevel = headOfNextLevel;
}
// Move to the next node in the same level
current = current.next;
}
}
}
http://www.acmerblog.com/leetcode-solution-populating-next-right-pointers-in-each-node-ii-6256.html10 | public void connect(TreeLinkNode root) { |
11 | TreeLinkNode head = root; |
12 | while(head != null){ |
13 | TreeLinkNode curNode = head; |
14 | TreeLinkNode tmpNextHead = new TreeLinkNode(0); |
15 | TreeLinkNode pre = tmpNextHead; |
16 | while(curNode != null){ |
17 | if(curNode.left != null){ |
18 | pre.next = curNode.left; |
19 | pre = pre.next; |
20 | } |
21 | if(curNode.right != null){ |
22 | pre.next = curNode.right; |
23 | pre = pre.next; |
24 | } |
25 | curNode = curNode.next; |
26 | } |
27 | head = tmpNextHead.next; |
28 | } |
29 | } |
public void connect(TreeLinkNode root) {
TreeLinkNode levelHead = root, nextLevelHead = null;
while (levelHead != null) {
TreeLinkNode node = levelHead, tail = null;
while (node != null) {
if (node.left != null && node.right != null) {
node.left.next = node.right;
}
TreeLinkNode sub;
if (node.left != null)
sub = node.left;
else if (node.right != null)
sub = node.right;
else
sub = null;
if (sub != null) {
if (nextLevelHead == null) {
nextLevelHead = sub;
tail = sub;
} else {
tail.next = sub;
}
while (tail.next != null)
tail = tail.next;
}
node = node.next;
}
levelHead = nextLevelHead;
nextLevelHead = null;
}
}http://www.cnblogs.com/springfor/p/3889327.html
public void connect(TreeLinkNode root) { if(root == null){ return; } if(root.right!=null){ root.right.next = findNext(root.next); } if(root.left!=null){ root.left.next = root.right==null?findNext(root.next):root.right; } connect(root.right); connect(root.left); } public TreeLinkNode findNext(TreeLinkNode root){ if(root==null){ return null; }else{ TreeLinkNode iter = root; TreeLinkNode result = null; while(iter!=null){ if(iter.left!=null){ result = iter.left; break; } if(iter.right!=null){ result = iter.right; break; } iter = iter.next; } return result; } } public void connect(TreeLinkNode root) {
if (root == null) return;
//如果右孩子不为空，左孩子的next是右孩子。
//反之，找root next的至少有一个孩子不为空的节点
if (root.left != null) {
if (root.right != null) {
root.left.next = root.right;
}
else {
TreeLinkNode p = root.next;
while (p != null && p.left == null && p.right == null)
p = p.next;
if (p != null)
root.left.next = p.left == null ? p.right : p.left;
}
}
//右孩子的next 根节点至少有一个孩子不为空的next
if (root.right != null) {
TreeLinkNode p = root.next;
while (p != null && p.left == null && p.right == null)
p = p.next;
if (p != null)
root.right.next = p.left == null ? p.right : p.left;
}
connect(root.right);
connect(root.left);
}
Related: Leetcode: Populating Next Right Pointers in Each Node I (java)Read full article from Leetcode: Populating Next Right Pointers in Each Node II (java) - Muscler的专栏 - 博客频道 - CSDN.NET
