144. Binary Tree Preorder Traversal
Easy LeetCodeGiven 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 = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [1,2,4,5,6,7,3,8,9]
Example 3
Input: root = []
Output: []
Example 4
Input: root = [1]
Output: [1]
Constraints
- The number of nodes in the tree is in the range [0, 100]
- -100 <= Node.val <= 100
How to solve the problem
Code
- DFS (Recursion)
Python
# 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]:
# Preorder: Root-Left-Right
ans = []
def dfs(node):
# Determine base case first(stop rucursion)
if node is None:
return
ans.append(node.val) # preorder
dfs(node.left) # left
dfs(node.right) # right
dfs(root)
return ans
- Iterations with stack
Python
# 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]:
# Determine base case first(stop rucursion)
if root is None:
return []
stack = [root] # Push root into stack first
result = [] # Define empty array
while stack:
node = stack.pop() # Popout root first
result.append(node.val) # Put the node which was poped out into result
# result.append(stack.pop().val)
if node.right:
stack.append(node.right) # Push right first, cause satck is FILO
if node.left:
stack.append(node.left) # Push left next, cause satck is FILO
return result
Complexity
- Time complexity: O(n), n == number of nodes
- Space complexity: O(n)
Comments
No comments yet. Be the first to comment!