Java O(1) Space O(n) Time Solution


  • 0
    K
    public class Solution {
        public void connect(TreeLinkNode root) {
            TreeLinkNode cur = root;
            TreeLinkNode nextlv = null;  // Start node at next level.
            while(cur!=null)
            {
                if(cur.left!=null && cur.right!=null)
                {
                    cur.left.next = cur.right;
                }
                if(nextlv == null) nextlv = (cur.left!=null)?cur.left:cur.right;
                if(cur.next!=null)
                {
                    // Left side node of the new link
                    TreeLinkNode pre = (cur.right!=null)?cur.right:cur.left;
                    if(pre!=null)
                    {
                        // Right side node of the new link
                        TreeLinkNode getnext = null;
                        while(getnext == null && cur.next!=null)
                        {
                            getnext = (cur.next.left != null)? cur.next.left:cur.next.right;
                            cur = cur.next;
                        }
                        pre.next = getnext;
                    }
                    else cur = cur.next;
                }
                else
                {
                    cur = nextlv;
                    nextlv = null;
                }
            }
        }
    }

Log in to reply
 

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