116. Populating Next Right Pointers In Each Node

Problem URL

Populating Next Right Pointers in Each Node

Description

Given a binary tree

struct TreeLinkNode {
   TreeLinkNode *left;
   TreeLinkNode *right;
   TreeLinkNode *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.

Note

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

Solution

When we solve the problem about Tree, we always think of recursion. Fortunately the tree is a perfect binary tree, so we can use many of its quality. We assume that a general tree is like this

     1
   /  \
  2    3
 / \  / \
4  5  6  7

the root 1 element has two children 2 and 3, they also have their own children, in order to line their children together, we have to do four things:

• line 2 and 3 together (2->3)
• line 2’s children 4 and 5 together (4->5)
• line 2’s right children 5 and 3’s left children 6 together (5->6)
• line 3’s children 6 and 7 together (6->7)

do those steps recursion, we can generate the whole tree. Here is the program in java.

program-01

public void connect(TreeLinkNode left,TreeLinkNode right){
	if(left!=null && right!=null){
		left.next=right;
		connect(left.left,left.right);
		connect(left.right,right.left);
		connect(right.left,right.right);
	}
}

Let’s explain them more detail. Imagine a larger tree who’s specific layer is like this

when we use function connect(a,b), we can connect a and b and both their children, and the function connect(b,c) will also connect b and c and their children at the same time, by this way, we will connect this layer node together. Its sample and useful.

---

But what if the tree is not a perfect tree? Maybe some children will not exists, so how can we connect them if they even not exists? Or can we modify this method and use the same idea to fix imperfect tree? The answer is NO (Why ? hiahia~).

So the next change is how to deal with the imperfect tree? Also see the problem in leedcode 117. Populating Next Right Pointers in Each Node II
Here we use Level Traverse.

Suppose we have come to this situation

The key point is that how can we line their children together?
We define three pointer:

• father: which point at the a,b,c,d,e node, we call it father pointer.
• son : which point at a,b,c,d,e node children, we can it son pointer.

when we traverse between father, we connect their son. Recursivly use this tech.

Program-02

while(father!=null){ //traverse the father.
	if(father.left!=null) { son.next=father.left;  son=son.next; }
	if(father.right!=null){ son.next=father.right; son=son.next; }
	father=father.next;
}

Program

Here we given the complete program about this two problems.

115 Perfect Tree Solution

public static void connect(TreeLinkNode root){
	if(root==null || (root.left==null && root.right==null)) return ;
	connect_1(root.left,root.right);
}
public void connect_1(TreeLinkNode left,TreeLinkNode right){
	if(left!=null && right!=null){
		left.next=right;
		connect_1(left.left,left.right);
		connect_1(left.right,right.left);
		connect_1(right.left,right.right);
	}
}

116 Imperfect Tree Solution

public static void connect_(TreeLinkNode root){
	TreeLinkNode level=new TreeLinkNode(0); 
	TreeLinkNode curr=level; level.next=root;
	while(root!=null){
		curr=level;
		while(root!=null){ 
			if(root.left!=null) { curr.next=root.left;  curr=curr.next; }
			if(root.right!=null){ curr.next=root.right; curr=curr.next; }
			root=root.next;
		}
		root=level.next;
		level.next=null;		
	}
}