Java Solution with O(n) time and O(1) space (27 lines)


  • 2

    Once you got the basic idea, it is easy to understand this solution.

    The most important thing to realize is that:

    Each level above the current level, is already a linked list!

    For example,

         1 -> NULL        level 1
        /  \
       2 -> 3 -> NULL     level 2
      / \    \
    4-> 5 -> 7 -> NULL    level 3
    

    Consider this tree. At first, link root to null; Thus level 1 is a linked list. Then we move on to level 2; and sicne level 1 is already a linked list, we can iterate each node in the linked list (just one node except null at this level), and link the children from left to right (), then link to null at the end. Moving on to level 3; level 2 is already a linked list, so we iterate each node (2, and 3), link their children from left to right (skip if the children is null, such as the left child of node 3), then link to null at the end. Same idea applies beyond.

    Thus, we just need to iterate each element of the above level, link their left and right nodes (if it has) in order, and then iterate through each level.

    The Java code is attached below: (~ 27 lines) It uses O(n) time and O(1) space.

    public class Solution {
        public void connect(TreeLinkNode root) {
            if (root == null) {
                return;
            }
            root.next = null;
            TreeLinkNode lasthead = root;
            TreeLinkNode dummy;
            TreeLinkNode cur;
            while (lasthead != null) {
                dummy = new TreeLinkNode(0);
                cur = dummy;
                while (lasthead!= null) {
                    if (lasthead.left != null) {
                        cur.next = lasthead.left;
                        cur = cur.next;
                    }
                    if (lasthead.right != null) {
                        cur.next = lasthead.right;
                        cur = cur.next;
                    }
                    lasthead = lasthead.next;
                }
                cur.next = null;
                lasthead = dummy.next;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.