as solution code


  • 0

    Solution1. Use next variable - time = O(n), space = O(1)

    The basic idea is to connect nextLevel nodes by traverse curLevel's left/right kids.
    Trick is to use dummyHead to append nextLevel nodes.

    NOTE:
    1) *Every loop sets nodes of the NEXT level, not the current level!
    2) Starts from the second level.

                                         root
                                    /           \
                                  l              r
                                /   \          /   \
     dummyHead(nextLevel) -> left -> right -> left->right
    
        func connect(_ root: TreeNode?) {
            var root = root
            while root != nil {
                let dummyHead = TreeNode(0)     // Dummy head of next level
                var cur: TreeNode = dummyHead   // Loop to set every next level node's next.
                while root != nil {             // 1. One level
                    if let left = root!.left {  // 1-1. root.left
                        cur.next = left
                        cur = cur.next!
                    }
                    if let right = root!.right {// 1-2. root.right
                        cur.next = right
                        cur = cur.next!
                    }
                    root = root!.next           // 1-3. <- Rightward: on cur level - l.left -> l.right -> r.left -> r.right
                }
                
                root = dummyHead.next           // 2. <-Next level: root.left
            }
        }
    

Log in to reply
 

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