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,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
116. Populating Next Right Pointers in Each Node的延续，如果给定的树是任何二叉树，不一定是完全二叉树，就是说不是每个节点都包含有两个子节点。
解法1：BFS, easy but not constant space, Complexity: time O(N) space O(N) - queue
解法2: Iteration - use dummy node to keep record of the next level's root to refer pre travel current level by referring to root in the level above，Complexity: time O(N) space O(1)
Java：BFS
class Solution {
public void connect(TreeLinkNode root) {
if(root == null)return;
Queue<TreeLinkNode> nodes = new LinkedList<>();
nodes.offer(root);
while(!nodes.isEmpty()){
int size = nodes.size();
for(int i = 0; i < size; i++){
TreeLinkNode cur = nodes.poll();
TreeLinkNode n = null;
if(i < size - 1){
n = nodes.peek();
}
cur.next = n;
if(cur.left != null)nodes.offer(cur.left);
if(cur.right != null)nodes.offer(cur.right);
}
}
}
}
Java: Iteration
class Solution {
public void connect(TreeLinkNode root) {
TreeLinkNode dummy = new TreeLinkNode(0);
TreeLinkNode pre = dummy;//record next root
while(root != null){
if(root.left != null){
pre.next = root.left;
pre = pre.next;
}
if(root.right != null){
pre.next = root.right;
pre = pre.next;
}
root = root.next;//reach end, update new root & reset dummy
if(root == null){
root = dummy.next;
pre = dummy;
dummy.next = null;
}
}
}
}
Java:
public void connect(TreeLinkNode root) {
if(root == null)
return;
TreeLinkNode lastHead = root;//prevous level's head
TreeLinkNode lastCurrent = null;//previous level's pointer
TreeLinkNode currentHead = null;//currnet level's head
TreeLinkNode current = null;//current level's pointer
while(lastHead!=null){
lastCurrent = lastHead;
while(lastCurrent!=null){
//left child is not null
if(lastCurrent.left!=null) {
if(currentHead == null){
currentHead = lastCurrent.left;
current = lastCurrent.left;
}else{
current.next = lastCurrent.left;
current = current.next;
}
}
//right child is not null
if(lastCurrent.right!=null){
if(currentHead == null){
currentHead = lastCurrent.right;
current = lastCurrent.right;
}else{
current.next = lastCurrent.right;
current = current.next;
}
}
lastCurrent = lastCurrent.next;
}
//update last head
lastHead = currentHead;
currentHead = null;
}
}
Python:
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
self.next = None def __repr__(self):
if self is None:
return "Nil"
else:
return "{} -> {}".format(self.val, repr(self.next)) class Solution:
# @param root, a tree node
# @return nothing
def connect(self, root):
head = root
while head:
prev, cur, next_head = None, head, None
while cur:
if next_head is None:
if cur.left:
next_head = cur.left
elif cur.right:
next_head = cur.right if cur.left:
if prev:
prev.next = cur.left
prev = cur.left if cur.right:
if prev:
prev.next = cur.right
prev = cur.right cur = cur.next
head = next_head
C++:
class Solution {
public:
void connect(TreeLinkNode *root) {
TreeLinkNode *dummy = new TreeLinkNode(0), *t = dummy;
while (root) {
if (root->left) {
t->next = root->left;
t = t->next;
}
if (root->right) {
t->next = root->right;
t = t->next;
}
root = root->next;
if (!root) {
t = dummy;
root = dummy->next;
dummy->next = NULL;
}
}
}
};
类似题目：
[LeetCode] 116. Populating Next Right Pointers in Each Node 每个节点的右向指针