Populating Next Right Pointers in Each Node I & 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

这道题本来只需要用一个arraylist来装每个level的node,然后再生成出linkedlist即可,但是这样的话我们会用到recursive call,而recursive call会需要n(logn)的stack空间(因为(logn)是树的高度),不满足constant的space的要求。

其实只需要把recursive call的内容放在一个while loop里实现,就成了constant space了。

具体方法是用上一层用来generate下一层。

首先有一个指针start指向每一层的第一个数,
通过第一个while loop找到本层的第一个有非空子树的Node:curr,这个数对应着下一层最左边的第一个Node:nextCurr,同时更新start = nextCurr的值,因为这个数就是下一层start的开始。
然后通过curr的linkedlist来更新nextCurr的linkedlist,当curr == null以后,nextCurr的linkedlist也就生成完毕了。
然后再通过更新过的start从新的一层开始。

/**
 * 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) {
        TreeLinkNode start = root;
        
        while(start != null)
        {
            TreeLinkNode nextCurr = null;
            TreeLinkNode curr = start;
            //find the first element for the next level linkedlist
            while(curr != null)
            {
                start = null; // if no branch is hit, start will be null
                if (curr.left == null && curr.right == null)
                {
                    curr = curr.next;
                    continue;
                }
                else if (curr.left == null)
                {
                    nextCurr = curr.right;
                    start = nextCurr;
                    curr = curr.next;
                    break;
                }
                else if (curr.right == null)
                {
                    nextCurr = curr.left;
                    start = nextCurr;
                    curr = curr.next;
                    break;
                }
                else
                {
                    curr.left.next = curr.right;
                    nextCurr = curr.right;
                    start = curr.left;
                    curr = curr.next;
                    break;
                }
            }
             // update next level start point
            // construct linked list for next level using the first element found
            while (curr != null)
            {
                if (curr.left == null && curr.right == null)
                {
                    
                }
                else if (curr.left == null)
                {
                    nextCurr.next = curr.right;
                    nextCurr = curr.right;
                }
                else if (curr.right == null)
                {
                    nextCurr.next = curr.left;
                    nextCurr = curr.left;
                }
                else
                {
                    nextCurr.next = curr.left;
                    curr.left.next = curr.right;
                    nextCurr = curr.right;
                }
                curr = curr.next;
            }
        }  
        return;
    }
}

Second Submission
Use BFS,scan every level, use two counters to count the number of node in current and next level. Pay attention that when counting the next level, the nCount increase must happen after the node been put into the fifo in order to record the new coming node in the current loop

/**
 * 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;
        LinkedList<TreeLinkNode> fifo = new LinkedList<TreeLinkNode>();
        fifo.add(root);
        int tCount = 1;
        int nCount = 0;
        while(!fifo.isEmpty()) {
            TreeLinkNode curr = fifo.removeFirst();
            if (curr.left != null) {
                fifo.add(curr.left);
                nCount++;
            }
            if (curr.right != null) {
                fifo.add(curr.right);
                nCount++;
            }
            tCount--;
            if(tCount == 0) { // last element of curr level
                tCount = nCount;
                nCount = 0;
                curr.next = null;
            }
            else
                curr.next = (fifo.isEmpty())? null : fifo.get(0); // if last char in the tree, set to null
        }
        return;
        
    }
}

A simpler solution is to use an ArrayList(LinkedList) for each level so you don’t need to keep track of the numbers using the same fifo. Should have thought of this!

Simpler solution, use two pointers to scan the level one by one (for perfect binary search tree (question I)

/**
 * 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 head = root;
        TreeLinkNode next = head.left;
        while(next != null) {
            //search current level with head
            while(head != null) {
                head.left.next = head.right;
                TreeLinkNode tmp = head.right;
                head = head.next;
                if (head != null)
                    tmp.next = head.left;
                else
                    tmp.next = null;
            }
            head = next;
            next = head.left;
        }
    }
}

Same idea, works for any binary tree

/**
 * 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 || (root.left == null && root.right == null))
            return;
        TreeLinkNode head = root;
        TreeLinkNode next = (root.left == null)? root.right : root.left;
        
        while(next != null) {
            TreeLinkNode tmp = null;
            next = null; // init next
            //scan current level with head
            while(head != null) {
                if (head.left != null) {
                    next = next == null? head.left : next;
                    if (tmp != null) // if not first in the level
                        tmp.next = head.left;
                    tmp = head.left;
                } 
                if (head.right != null) {
                    next = next == null? head.right : next;
                    if (tmp != null) // if not first in the level
                        tmp.next = head.right;
                    tmp = head.right;
                }
                head = head.next;
            }
            head = next;
        }
    }
}

use recursion and a dummy node. works for any binary tree, use a dummy node and a prev pointer to track the next level.

/**
 * 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 dummy = new TreeLinkNode(-1); // create a dummy node for next level
        TreeLinkNode curr = root; // pointer for this level
        TreeLinkNode pre = dummy; // pre for next level
        while(curr != null) {
            if (curr.left != null) {
                pre.next = curr.left;
                pre = curr.left;
            }
            if (curr.right != null) {
                pre.next = curr.right;
                pre = curr.right;
            }
            curr = curr.next;
        }
        connect(dummy.next);
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s