ac solution code

• 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
}
``````

``````/*
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
}

``````

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