2 Iterative Time O(N) C# Solution - A Space(1) & A BFS Space O(N) with explanations


  • 0
    L

    The first solution is to connect the next pointers of child-level nodes by looping each parent-level nodes
    from left to right

    public void connect(TreeLinkNode root) {
        while (root != null){
            //1. Use root to identify the parent level most left head
            while (root != null && root.left == null && root.right == null) root = root.next;
            TreeLinkNode parentCur = root, childHead = null, childCur = null, childNext;
    
            //2. Use childHead to identify the child-level most left head
            if (root != null)
                childCur = childHead = root.left != null ? root.left : root.right;
    
            //3. Loop parent-level from left to right to connect children's next pointers
            while (parentCur != null){
                if(parentCur.left != null && parentCur.left != childCur){
                    childNext = parentCur.left;
                    childCur.next = childNext;
                    childCur = childNext;
                }
                if(parentCur.right != null && parentCur.right != childCur){
                    childNext = parentCur.right;
                    childCur.next = childNext;
                    childCur = childNext;
                }
                parentCur = parentCur.next;
            }
            //4. Loop to next level
            root = childHead;
        }
    }
    

    The 2nd solution is to use a Queue to do Horizontal-Level BFS connecting

    public void connect2(TreeLinkNode root) {
        Queue<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();
        if(root != null) queue.offer(root);
        for(int level = 1, curLevel = 0; !queue.isEmpty(); level = curLevel, curLevel = 0){
            TreeLinkNode curParent = queue.poll();
            level--;
            if (curParent.left != null) { queue.offer(curParent.left); curLevel++; }
            if (curParent.right != null) { queue.offer(curParent.right); curLevel++; }
            while (level > 0){
                TreeLinkNode curChild = queue.poll();
                level--;
                if (curChild.left != null) { queue.offer(curChild.left); curLevel++; }
                if (curChild.right != null) { queue.offer(curChild.right); curLevel++; }
                curParent.next = curChild;
                curParent = curChild;
            }
        }
    }

Log in to reply
 

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