ac solution code


  • 0

    Pre-order: root, left, right

    Explanation:

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

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

    The basic idea is similar as in-order traversal, as preorder sequence is root, left, right, the only difference is append each passed node's value to the result array during traveling to the left leaf, instead of after reaching the tree's left leaf.

    /*
    Solution1. Iterative: Stack. time = O(n) - each node is visited once; space = O(n)
    */
       func preorderTraversal(_ 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 left branch to stack until leaf
                   res.append(cur!.val)    // Append cur's val
                   stack.push(cur!)        // Push cur to stack
                   cur = cur!.left         // cur = cur.left
               } else {
                   cur = stack.pop()       // 2. Backtrack to higher level node A (stack isn't empty, via while/if condition)
                   cur = cur!.right        // 3. Switch to the higher node A's right branch
               }
           }
           return res
       }
    

    0_1485208397916_Pre-order.png

    /*
         Solution2. Translate from reclusive 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 preorderTraversal(_ 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.append(curr.val)
                if curr.right != nil{           // <--Push: curr.right earlier than curr.left (Stack reverses order of execution)
                    stack.push(curr.right!)
                }
                if curr.left != nil {           // Push: curr.left
                    stack.push(curr.left!)
                }
            }
            return res
        }
    
    

Log in to reply
 

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