ac solution code


  • 0

    The solution is based on Preorder traversal:

    /*
         Solution1. Iterative - Stack. time = O(n) - each node is visited once; space = O(n) - stack
        
         Translate recursive function to stack step by step, as it is. Preorder traversal: root, left, right:
         Push: root
         1. Pop : curr = stack.pop()
         2. Push: curr's right, if exists                   // RIGHT
         3. Push: curr's left, if exists                    // LEFT
         4. 1) Peek: curr's right = stack.peek() - prev     // ROOT: update curr's right/left
             2) curr.left = nil
         Keep the above steps.
         */
        func flatten1(_ root: TreeNode?) {
            guard let root = root else {return}
            var stack = Stack<TreeNode>()
            stack.push(root)
    
            while !stack.isEmpty() {
                let curr = stack.pop()!         // POP: the last pushed node
                if curr.right != nil{           // PUSH: curr.right (NOTE: push curr's right first, as stack reverses execution order)
                    stack.push(curr.right!)
                }
                if curr.left != nil {           // PUSH: curr.left
                    stack.push(curr.left!)
                }
                if !stack.isEmpty() {
                    curr.right = stack.peek()   // prev - root's next: its left if its left exists; its right if its left doesn't exist
                }
                curr.left = nil                 // Don't forget this!!
            }
        }
    
        /*
         Solution2. Recursive - time = O(n) - each node is visited once; space = O(n) - stack
         Reverse process of Pre-order: RIGHT, LEFT, ROOT (to avoid changing node's left/right for the later use)
    
         1) Reverse Pre-order traversal: RIGHT, LEFT, ROOT (travel to right leaf first)
         2) a) curr's right(next) = prev;
             b) curr's left = nil
         3) prev = root
         */
        private var prev: TreeNode?
        func flatten(_ root: TreeNode?) {
            guard let root = root else {return}
            flatten(root.right)     // Flatten root'right tree
            flatten(root.left)      // Flatten root'left tree
            root.right = prev       // Connect root.next with the previous answer
            root.left = nil
            prev = root             // Store root to prev, then keep recursion
        }
    

    0_1485315964511_FlattenBinaryTreeToLinkedList.png


Log in to reply
 

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