« Back
in Leetcode Java Tree Depth-first Search read.

Leetcode 117 Populating Next Right Pointers in Each Node II.

Problem 117 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

A very interesting problem, similar to Populating Next Right Pointers in Each Node.

But as the tree have possibility that is not a full tree, so we have to consider the problem from the right side. Use a point to determine the right one we should connect to, then do from the left.

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if(root==null){
            return;
        }

        TreeLinkNode p=root.next;

        while(p!=null){
            if(p.left!=null){
                p=p.left;
                break;
            }
            if(p.right!=null){
                p=p.right;
                break;
            }
            p=p.next;
        }

        if(root.right!=null){
            root.right.next = p;
        }
        if(root.left!=null){
            if(root.right!=null){
                root.left.next=root.right;
            }else{
                root.left.next=p;
            }

            //root.left.right.next=root.right.left;
        }




        connect(root.right);        
        connect(root.left);

    }
}
comments powered by Disqus