94. Binary Tree Inorder Traversal
Given 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 = [] Output: []
Example 3:
Input: root = [1] Output: [1]
Example 4:
Input: root = [1,2] Output: [2,1]
Example 5:
Input: root = [1,null,2] Output: [1,2]
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?
Source
In [1]:
# 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
Code
In [2]:
def inorder_traversal(root):
if not root:
return None
def helper(node):
if not node:
return
nonlocal traversal
helper(node.left)
traversal.append(node.val)
helper(node.right)
traversal = []
helper(root)
return traversal
Follow up:
Solve it both recursively and iteratively.
Code
In [ ]:
def inorder_traversal(root):
"""Inorder iterative. using 2 stacks"""
stack = []
traversal = []
node = root
while node or stack:
while node: # go to the leftmost child
stack.append(node)
node = node.left
# if no more left child, get the 1st right node and check for leftmost child again
node = stack.pop()
traversal.append(node.val) # print
node = node.right
return traversal
In [ ]:
def inorder_traversal(root):
"""Single loop alternative using 2 stacks"""
stack = []
traversal = []
node = root
while stack or node:
if node:
stack.append(node)
node = node.left
else:
tmp_node = stack.pop()
traversal.append(tmp_node.val) # print
node = tmp_node.right
return traversal
In [ ]:
from collections import deque
def inorder_traversal(root):
"""Inorder iterative. using 1 stack + 1 queue"""
stack = []
traversal = deque()
node = root
while node or stack:
# travel to each node's left child until leaf
while node:
stack.append(node)
node = node.left
node = stack.pop()
traversal.appendleft(node.val) # print
node = node.right
return reversed(traversal)
In [ ]:
from collections import deque
def inorder_traversal(root):
"""Single loop alternative 1 stack + 1 queue"""
stack = []
traversal = deque()
node = root
while stack or node:
if node:
stack.append(node)
node = node.left
else:
tmp_node = stack.pop()
traversal.appendleft(tmp_node.val) # print
node = tmp_node.right
return reversed(traversal)