ac solution code


  • 0

    Solution. Iterative: Stack. time = O(n) - each node is visited once; space = O(n)

    Explanation

    Postorder: left, right, root
    Preorder : root, right, left

    Postorder is kind of reverse order of Preorder. (Just travel to tree's right leaf at first, instead of left leaf).

    1. Start from root, recursively travel to each passed node's right child until reach the tree's right leaf
    2. Then pop to right leaf's higher level node A
    3. And switch to A's left branch

    Keep the above steps until the current node is null and stack is empty.

    Trick: Add node's value to array's first position to reverse the order.

    /*
    Solution1. Iterative: Stack. time = O(n) - each node is visited once; space = O(n)
    */
        func postorderTraversal(_ root: TreeNode?) -> [Int] {
            var res = [Int]()
            var stack = Stack<TreeNode>()
            var cur: TreeNode? = root           // Set `root` as `cur`
            
            while cur != nil || !stack.isEmpty {// <-- !stack.isEmpty
                if cur != nil {                 // 1. Push cur's RIGHT branch to stack until leaf
                    res.insert(cur!.val, at: 0) // 2. Insert cur's val at 0
                    stack.push(cur!)
                    cur = cur!.right
                } else {
                    cur = stack.pop()           // 3. Backtrack to higher level node A (stack isn't empty, via while/if condition)
                    cur = cur!.left             // 4. Switch to the higher node A's LEFT branch
                }
            }
            return res
        }
    
    

    0_1485208189507_Post-order.png

        /*
         Solution2. Translate from recusive solution. time = O(n) - each node is visited once; space = O(n)
         CAN'T BE USED for in-order traversal, because root poping is after all left nodes poping (root poping is at beginning for Pre/Post traversal)
         */
        func postorderTraversal(_ root: TreeNode?) -> [Int] {
            var res = [Int]()
            guard let root = root else {return res}
            var stack = Stack<TreeNode>()
            stack.push(root)                    // Push: root
    
            while !stack.isEmpty() {
                let curr = stack.pop()!         // Pop: the last pushed node
                res.insert(curr.val, at: 0)     // <--insert at 0
                if curr.left != nil {           // Push: curr.left
                    stack.push(curr.left!)
                }
                if curr.right != nil{           // <--Push: curr.right later than curr.left (Stack reverses order of execution)
                    stack.push(curr.right!)
                }
            }
            return res
        }
    

Log in to reply
 

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