O(1) space O(n) complexity Iterative Solution with Explanation


  • 0
    L

    We build a linked list for each row, level by level, from top to bottom.

    We start from the first level, there is only an element: root, it's already a linked list which only contains an element.

    We use a variable current to make the pointer of the current rows linked list. We can use current = current.next to iterate the whole list.

    Now we will build the linked list for next row. We use nextRowDummyHead to represent the sentinel of the linked list, so nextRowDummyHead.next will be the head of the linked list. We use nextRowCurrentNode to represent the current node.

    We check the left and right children for each current, we can link them to the tail of the next row's linked list.

    public void connect(TreeLinkNode root) {
        
        TreeLinkNode current = root;
        TreeLinkNode nextRowDummyHead = null;
        TreeLinkNode nextRowCurrentNode = null;
        
        while (current != null) {
            
            nextRowDummyHead = new TreeLinkNode(0);
            nextRowCurrentNode = nextRowDummyHead;
            
            while (current != null) {
            
                // if left child is not null, link it to the tail
                if (current.left != null) {
                    nextRowCurrentNode.next = current.left;
                    nextRowCurrentNode = nextRowCurrentNode.next;
                }
            
                // link the right node to the tail if it's not null
                if (current.right != null) {
                    nextRowCurrentNode.next = current.right;
                    nextRowCurrentNode = nextRowCurrentNode.next;
                }
                // move to next
                current = current.next;
            }
            
            // move to next level
            current = nextRowDummyHead.next;
        }
    }

Log in to reply
 

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