All Traversal¶
Depth First Search¶
144. Binary Tree Preorder Traversal (Easy)¶
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def recursion(node):
if node:
nodes.append(node.val)
recursion(node.left) if node.left else None
recursion(node.right) if node.right else None
nodes = []
recursion(root)
return nodes
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
nodes = []
stack = [(root, False)]
while stack:
node, visited = stack.pop()
if node:
if visited:
nodes.append(node.val)
else:
stack.append((node.right, False))
stack.append((node.left, False))
stack.append((node, True))
return nodes
94. Binary Tree Inorder Traversal (Easy)¶
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def recursion(node):
if node:
recursion(node.left) if node.left else None
nodes.append(node.val)
recursion(node.right) if node.right else None
nodes = []
recursion(root)
return nodes
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
nodes = []
stack = [(root, False)]
while stack:
node, visited = stack.pop()
if node:
if visited:
nodes.append(node.val)
else:
stack.append((node.right, False))
stack.append((node, True))
stack.append((node.left, False))
return nodes
145. Binary Tree Postorder Traversal (Easy)¶
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def recursion(node):
if node:
recursion(node.left) if node.left else None
recursion(node.right) if node.right else None
nodes.append(node.val)
nodes = []
recursion(root)
return nodes
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
nodes = []
stack = [(root, False)]
while stack:
node, visited = stack.pop()
if node:
if visited:
nodes.append(node.val)
else:
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
return nodes
Breadth First Search / Level Order¶
102. Binary Tree Level Order Traversal (Medium)¶
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
def recursion(node):
nonlocal cur_depth
if node:
cur_depth += 1
hm[cur_depth].append(node.val)
recursion(node.left)
recursion(node.right)
cur_depth -= 1
cur_depth = 0
hm = defaultdict(list)
recursion(root)
return list(hm.values())
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
hm = collections.defaultdict(list)
queue = [root]
next_queue = []
level = 0
while queue:
while queue:
node = queue.pop(0)
if node:
hm[level].append(node.val)
next_queue.append(node.left) if node.left else None
next_queue.append(node.right) if node.right else None
queue = next_queue
next_queue = []
level += 1
return list(hm.values())
107. Binary Tree Level Order Traversal II (Medium)¶
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
def recursion(node):
nonlocal cur_depth
if node:
cur_depth += 1
hm[cur_depth].append(node.val)
recursion(node.left)
recursion(node.right)
cur_depth -= 1
cur_depth = 0
hm = defaultdict(list)
recursion(root)
return reversed(list(hm.values()))
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
hm = collections.defaultdict(list)
queue = [root]
next_queue = []
level = 0
while queue:
while queue:
node = queue.pop(0)
if node:
hm[level].append(node.val)
next_queue.append(node.left) if node.left else None
next_queue.append(node.right) if node.right else None
queue = next_queue
next_queue = []
level += 1
return reversed(list(hm.values()))
103. Binary Tree Zigzag Level Order Traversal (Medium)¶
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
isEven = lambda x: x % 2 == 0
def recursion(node):
nonlocal level
if node:
level += 1
if isEven(level):
hm[level].append(node.val)
else:
hm[level].insert(0, node.val)
recursion(node.left) if node.left else None
recursion(node.right) if node.right else None
level -= 1
level = -1
hm = collections.defaultdict(list)
recursion(root)
return list(hm.values())
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
isEven = lambda x: x % 2 == 0
hm = collections.defaultdict(list)
queue = [root]
next_queue = []
level = 0
while queue:
while queue:
node = queue.pop(0)
if node:
if isEven(level):
hm[level].append(node.val)
else:
hm[level].insert(0, node.val)
next_queue.append(node.left) if node.left else None
next_queue.append(node.right) if node.right else None
queue = next_queue
next_queue = []
level += 1
return list(hm.values())
Vertical Order¶
987. Vertical Order Traversal of a Binary Tree (Hard)¶
def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
def recursion(node):
nonlocal hm, col, row, min_col, max_col
if node:
# Get the range of the column number
min_col = min(min_col, col)
max_col = max(max_col, col)
# Append val into [col][row]
hm[col][row] = hm[col].get(row, []) + [node.val]
# Preorder (go left)---------------------
col, row = col - 1, row + 1 # a
recursion(node.left)
col, row = col + 1, row - 1 # a backtrack
# Preorder (go right) -------------------
col, row = col + 1, row + 1 # b
recursion(node.right)
col, row = col - 1, row - 1 # b backtrack
hm = defaultdict(dict)
min_col = max_col = col = row = 0
recursion(root)
# Extract the list of values by sorting the list based on <row,value>
ans = []
for col in range(min_col, max_col + 1):
ans.append([j for row in sorted(hm[col]) for j in sorted(hm[col][row])])
return ans
def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
hm = collections.defaultdict(dict)
stack = [(root, 0, 0)]
while stack:
node, row, col = stack.pop()
if node:
hm[col][row] = hm[col].get(row, []) + [node.val]
stack.append((node.right, row + 1, col + 1)) if node.right else None
stack.append((node.left, row + 1, col - 1)) if node.left else None
nodes = []
for col in sorted(hm):
nodes.append([val for row in sorted(hm[col]) for val in sorted(hm[col][row])])
return nodes
def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
hm = {}
stack = [(root, 0, 0)]
min_col = 10001
min_rows = {}
max_rows = {}
while stack:
node, row, col = stack.pop()
if node:
if col not in hm:
hm[col] = {}
min_rows[col] = 10001
max_rows[col] = -1
if row not in hm[col]:
hm[col][row] = []
hm[col][row].append(node.val)
min_col = min(min_col, col)
min_rows[col] = min(min_rows[col], row)
max_rows[col] = max(max_rows[col], row)
stack.append((node.right, row + 1, col + 1)) if node.right else None
stack.append((node.left, row + 1, col - 1)) if node.left else None
nodes = []
for col in range(min_col, min_col + len(hm) + 1):
if col in hm:
nodes.append([])
for row in range(min_rows[col], max_rows[col] + 1):
row_nodes = hm.get(col, {}).get(row, [])
if row_nodes:
nodes[-1].extend(sorted(row_nodes))
return nodes
314. Binary Tree Vertical Order Traversal (Medium)¶
def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
def recursion(node):
nonlocal hm, col, row, min_col, max_col
if node:
# Get the range of the column number
min_col = min(min_col, col)
max_col = max(max_col, col)
# Append val into [col][row]
hm[col][row] = hm[col].get(row, []) + [node.val]
# Preorder (go left)---------------------
col, row = col - 1, row + 1 # a
recursion(node.left)
col, row = col + 1, row - 1 # a inverted
# Preorder (go right) -------------------
col, row = col + 1, row + 1 # b
recursion(node.right)
col, row = col - 1, row - 1 # b inverted
hm = defaultdict(dict)
min_col = max_col = col = row = 0
recursion(root)
# Extract the list of values by sorting the list based on <row,value>
ans = []
for col in range(min_col, max_col + 1):
ans.append([j for row in sorted(hm[col]) for j in hm[col][row]])
return ans if root else []
def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
hm = collections.defaultdict(dict)
stack = [(root, 0, 0)]
while stack:
node, row, col = stack.pop()
if node:
hm[col][row] = hm[col].get(row, []) + [node.val]
stack.append((node.right, row + 1, col + 1)) if node.right else None
stack.append((node.left, row + 1, col - 1)) if node.left else None
nodes = []
for col in sorted(hm):
nodes.append([val for row in sorted(hm[col]) for val in hm[col][row]])
return nodes
def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
hm = {}
stack = [(root, 0, 0)]
min_col = 10001
min_rows = {}
max_rows = {}
while stack:
node, row, col = stack.pop()
if node:
if col not in hm:
hm[col] = {}
min_rows[col] = 10001
max_rows[col] = -1
if row not in hm[col]:
hm[col][row] = []
hm[col][row].append(node.val)
min_col = min(min_col, col)
min_rows[col] = min(min_rows[col], row)
max_rows[col] = max(max_rows[col], row)
stack.append((node.right, row + 1, col + 1)) if node.right else None
stack.append((node.left, row + 1, col - 1)) if node.left else None
nodes = []
for col in range(min_col, min_col + len(hm) + 1):
if col in hm:
nodes.append([])
for row in range(min_rows[col], max_rows[col] + 1):
row_nodes = hm.get(col, {}).get(row, [])
if row_nodes:
nodes[-1].extend(row_nodes)
return nodes