Populating Next Right Pointers in Each Node II

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

This question is more difficult than the first "populating next right pointers in each node", which applies to a perfect binary search tree. In contrast, this tree can be any tree. However, it is not that difficult. Just find the next node that you can point to, by looking up the neighbors on the parent node. Find the first node that has a child, and set its first child to the next of your current node.

There is one thing you need to pay attention when you do the recursive call. Remember to apply the connect function on the right child of the current node first. So that you won't loose any connection at the parent level, before you handle the child nodes.

Java语言: PopulatingNextRightII

01 public class Solution {
02     public void connect(TreeLinkNode root) {
03         if(root==null)
04             return;
05         if(root.left!=null)
06         {
07             if(root.right!=null)
08             {
09                 root.left.next=root.right;
10             }
11             else
12             {
13                 TreeLinkNode temp=root.next;
14                 //find the first non-empty neighbor on parent level
15                 while(temp!=null && temp.left==null && temp.right==null)
16                 {
17                     temp=temp.next;
18                 }
19                 if(temp!=null)
20                 {
21                     if(temp.left!=null)
22                     {
23                         root.left.next=temp.left;
24                     }
25                     else
26                     {
27                         root.left.next=temp.right;
28                     }
29                 }
30             }
31         }
32       
33         if(root.right!=null)
34         {
35             TreeLinkNode tmp=root.next;
36             while(tmp!=null && tmp.left==null && tmp.right==null)
37             {
38                 tmp=tmp.next;
39             }
40           
41             if(tmp!=null)
42             {
43                 if(tmp.left!=null)
44                 {
45                     root.right.next=tmp.left;
46                 }
47                 else
48                 {
49                     root.right.next=tmp.right;
50                 }
51             }
52           
53         }
54     
55         //Connect right tree first
56         //so that you can resolve the next pointers on parent level
57         connect(root.right);
58         connect(root.left);      
59     }
60 }