144. Binary Tree Preorder Traversal
Easy
Given the root of a binary tree, return the preorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3] Output: [1,2,3]
Example 2:
Input: root = [] Output: []
Example 3:
Input: root = [1] Output: [1]
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# recursive
# l = []
# self.preorder(root, l)
# return l
# def preorder(self, root, l):
# if not root:
# return root
# if root:
# l.append(root.val)
# self.preorder(root.left, l)
# self.preorder(root.right, l)
# iterative
stack, output = [root], []
while stack:
item = stack.pop()
if item is not None:
output.append(item.val)
if item.right is not None:
stack.append(item.right)
if item.left is not None:
stack.append(item.left)
return output