Given the root of a binary tree, return the list of node values in preorder: each node is listed before everything in its left subtree, which is listed before everything in its right subtree. Try to do it without recursion, using an explicit stack.
Examples
1
/ \
2 3
/ \ \
4 5 6
Input: root = build_tree([1, 2, 3, 4, 5, None, 6])
Output: [1, 2, 4, 5, 3, 6]
Input: root = build_tree([])
Output: []
Constraints
0 <= number of nodes <= 2000-10**4 <= node.val <= 10**4- Target complexity: O(n) time.
Goals
- Produce the preorder sequence (node, left subtree, right subtree)
- Replace recursion with an explicit stack
- Handle the empty tree