Simple O(1) space non-recursive Java solution


  • 0
    R

    It just like the previous problem, except you can't always assume the new starting node in the next level is always be the left child of the current starting node. So we cache the first child in the next level to be the next starting node.

    For the left to right iteration, we also need to cache the previous node pending for connection.

    public class Solution {
        TreeLinkNode pending, firstChild;
        
        public void connect(TreeLinkNode root) {
            TreeLinkNode start = root;
            while (start != null) {
                pending = null;
                firstChild = null;
                for (TreeLinkNode i = start; i != null; i = i.next) {
                    walk(i.left);
                    walk(i.right);
                }
                start = firstChild;
            }
        }
        
        private void walk(TreeLinkNode child) {
            if (child == null) { return; }
            if (pending != null) { pending.next = child; }
            if (firstChild == null) { firstChild = child; }
            pending = child;
        }
    }
    

Log in to reply
 

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