Binary Tree Preorder Traversal
Given the root of a binary tree, return the preorder traversal of its nodes' values.
Follow up: Recursive solution is trivial, could you do it iteratively?
Example 1
1
\
2
/
3Input
root = [1,null,2,3]Output
[1,2,3]The preorder traversal visits the root
1, then the left subtree, then the right subtree containing 2 and 3.Example 2
1
/ \
2 3
/ \ \
4 5 8
/ \ /
6 7 9Input
root = [1,2,3,4,5,null,8,null,null,6,7,9]Output
[1,2,4,5,6,7,3,8,9]The preorder traversal visits each node before its children, producing the listed order.
Constraints
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100