94. Binary Tree Inorder Traversal
Easy LeetCodeGiven the root of a binary tree, return the inorder traversal of its nodes' values.
Example 1
Input: root = [1,null,2,3]
Output: [1,3,2]
Example 2
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,2,6,5,7,1,3,9,8]
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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# Inorder: Left-Root-Right
ans = []
def dfs(node):
# Determine base case first(stop rucursion)
if node is None:
return
dfs(node.left) # left
ans.append(node.val) # inorder
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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# Inorder: Left-Root-Right
stack = []
result = []
current = root
while current or stack:
if current:
stack.append(current) # Push every node traversed into stack
current = current.left # Go to the very left node
else: # when current is None (means left node finished)
current = stack.pop() # Pop out the current node, the very left one
result.append(current.val)
current = current.right # Then traverse right node
return result
Complexity
- Time complexity: O(n), n == number of nodes
- Space complexity: O(n)
Comments
No comments yet. Be the first to comment!