Height, Path, Views
Height
What's the difference between Depth and Height?
104. Maximum Depth of Binary Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
def maxDepth(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if not node:
return 0
left_depth = dfs(node.left)
right_depth = dfs(node.right)
return 1 + max(left_depth, right_depth)
return dfs(root)
Analysis
- Python
def maxDepth(self, root: Optional[TreeNode]) -> int:
stack = [(root, 1)]
depth = 0
while stack:
node, level = stack.pop()
if node:
depth = max(depth, level)
stack.append((node.left, level + 1))
stack.append((node.right, level + 1))
return depth
Analysis
- Python
def maxDepth(self, root: Optional[TreeNode]) -> int:
queue = collections.deque([root])
level = 0
while queue:
level += 1
for _ in range(len(queue)):
node = queue.popleft()
if node:
queue.append(node.left)
queue.append(node.right)
return level - 1
111. Minimum Depth of Binary Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
def minDepth(self, root: Optional[TreeNode]) -> int:
def dfs(node):
nonlocal mini, depth
if not node:
return 0
depth += 1
if not node.left and not node.right:
mini = min(mini, depth)
dfs(node.left)
dfs(node.right)
depth -= 1
mini = float("inf")
depth = 0
dfs(root)
return mini if mini != float("inf") else 0
Analysis
- Python
def minDepth(self, root: Optional[TreeNode]) -> int:
stack = [(root, False)]
mini = float("inf")
depth = 0
while stack:
node, visited = stack.pop()
if node:
if visited:
depth -= 1
else:
depth += 1
if not node.left and not node.right:
mini = min(mini, depth)
stack.append((node, True))
stack.append((node.left, False))
stack.append((node.right, False))
return mini if mini != float("inf") else 0
Analysis
- Python
def minDepth(self, root: Optional[TreeNode]) -> int:
queue = collections.deque([root])
level = 0
while queue:
level += 1
for _ in range(len(queue)):
node = queue.popleft()
if node:
if not node.left and not node.right:
return level
queue.append(node.left)
queue.append(node.right)
return level - 1
Path
112. Path Sum
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def dfs(node, total):
if not node:
return False
total += node.val
if not node.left and not node.right:
return total == targetSum
return dfs(node.left, total) or dfs(node.right, total)
return dfs(root, 0) if root else False
Analysis
- Python
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
stack = [(root, 0)]
while stack:
node, total = stack.pop()
if node:
total += node.val
if not node.left and not node.right and total == targetSum:
return True
stack.append((node.right, total))
stack.append((node.left, total))
return False
Analysis
- Python
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
queue = collections.deque([(root, 0)])
while queue:
for _ in range(len(queue)):
node, total = queue.popleft()
if node:
total += node.val
if not node.left and not node.right and total == targetSum:
return True
queue.append((node.left, total))
queue.append((node.right, total))
return False
113. Path Sum II
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
def dfs(node):
nonlocal path_sum
if node:
path_sum += node.val
path.append(node.val)
if not node.left and not node.right and path_sum == targetSum:
result.append(deepcopy(path))
dfs(node.left)
dfs(node.right)
path.pop()
path_sum -= node.val
path = []
path_sum = 0
result = []
dfs(root)
return result
Analysis
- Python
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
stack = [(root, False)]
path = []
path_sum = 0
result = []
while stack:
node, visited = stack.pop()
if node:
if visited:
path.pop()
path_sum -= node.val
else:
path_sum += node.val
path.append(node.val)
if not node.left and not node.right and path_sum == targetSum:
result.append(deepcopy(path))
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
return result
Analysis
- Python
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
queue = collections.deque([(root, 0, [])])
result = []
while queue:
for _ in range(len(queue)):
node, path_sum, path = queue.popleft()
if node:
path_sum += node.val
new_path = path + [node.val]
if not node.left and not node.right and path_sum == targetSum:
result.append(deepcopy(new_path))
queue.append((node.left, path_sum, new_path))
queue.append((node.right, path_sum, new_path))
return result
257. Binary Tree Paths
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
def dfs(node):
if node:
path.append(str(node.val))
if not node.left and not node.right:
result.append(deepcopy(path))
dfs(node.left)
dfs(node.right)
path.pop()
path = []
result = []
dfs(root)
return ["->".join(root_to_leaf) for root_to_leaf in result]
Analysis
- Python
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
stack = [(root, False)]
path = []
result = []
while stack:
node, visited = stack.pop()
if node:
if visited:
path.pop()
else:
path.append(str(node.val))
if not node.left and not node.right:
result.append(deepcopy(path))
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
return ["->".join(root_to_leaf) for root_to_leaf in result]
Analysis
- Python
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
queue = collections.deque([(root, [])])
result = []
while queue:
for _ in range(len(queue)):
node, path = queue.popleft()
if node:
new_path = path + [str(node.val)]
if not node.left and not node.right:
result.append(deepcopy(new_path))
queue.append((node.left, new_path))
queue.append((node.right, new_path))
return ["->".join(root_to_leaf) for root_to_leaf in result]
Root to leaf paths sum
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
def treePathSum(self, root):
def dfs(node):
nonlocal path, total
if node:
path = path * 10 + node.data
if not node.left and not node.right:
total += path
dfs(node.left)
dfs(node.right)
path = (path - node.data) // 10
path = total = 0
dfs(root)
return total
Analysis
- Python
def treePathSum(self, root):
stack = [(root, False)]
path = total = 0
while stack:
node, visited = stack.pop()
if node:
if visited:
path = (path - node.data) // 10
else:
path = path * 10 + node.data
if not node.left and not node.right:
total += path
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))
return total
Analysis
- Python
def treePathSum(self, root):
queue = collections.deque([(root, 0)])
total = 0
while queue:
for _ in range(len(queue)):
node, path = queue.popleft()
if node:
path = path * 10 + node.data
if not node.left and not node.right:
total += path
queue.append((node.left, path))
queue.append((node.right, path))
return total
Views
Left View of Binary Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
def LeftView(self, root):
def dfs(node, level):
if not node:
return
if level not in left_view:
left_view[level] = node.data
dfs(node.left, level + 1)
dfs(node.right, level + 1)
left_view = {}
dfs(root, 0)
return list(left_view.values())
Analysis
- Python
def LeftView(self, root):
stack = [(root, 1)]
left_view = {}
while stack:
node, level = stack.pop()
if node:
if level not in left_view:
left_view[level] = node.data
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return list(left_view.values())
Analysis
- Python
def LeftView(self, root):
queue = collections.deque([root])
left_view = {}
level = 0
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
if level not in left_view:
left_view[level] = node.data
queue.append(node.left)
queue.append(node.right)
level += 1
return list(left_view.values())
Right View of Binary Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
def rightView(self, root):
def dfs(node, level):
if not node:
return
right_view[level] = node.data
dfs(node.left, level + 1)
dfs(node.right, level + 1)
right_view = {}
dfs(root, 0)
return list(right_view.values())
Analysis
- Python
def rightView(self, root):
stack = [(root, 1)]
right_view = {}
while stack:
node, level = stack.pop()
if node:
right_view[level] = node.data
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return list(right_view.values())
Analysis
- Python
def rightView(self, root):
queue = collections.deque([root])
right_view = {}
level = 0
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
right_view[level] = node.data
queue.append(node.left)
queue.append(node.right)
level += 1
return list(right_view.values())
Top View of Binary Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
def topView(self, root):
def dfs(node, level, col):
nonlocal min_col, max_col
if not node:
return
min_col, max_col = min(min_col, col), max(max_col, col)
if col not in top_view or level < top_view[col][1]:
top_view[col] = node.data, level
dfs(node.left, level + 1, col - 1)
dfs(node.right, level + 1, col + 1)
min_col, max_col = float("inf"), -float("inf")
top_view = {}
dfs(root, 0, 0)
return [top_view[i][0] for i in range(min_col, max_col + 1)]
Analysis
- Python
def topView(self, root):
stack = [(root, 0, 0)]
min_col, max_col = float("inf"), -float("inf")
top_view = {}
while stack:
node, level, col = stack.pop()
if node:
min_col, max_col = min(min_col, col), max(max_col, col)
if col not in top_view or level < top_view[col][1]:
top_view[col] = node.data, level
stack.append((node.right, level + 1, col + 1))
stack.append((node.left, level + 1, col - 1))
return [top_view[i][0] for i in range(min_col, max_col + 1)]
Analysis
- Python
def topView(self, root):
queue = collections.deque([(root, 0)])
min_col, max_col = float("inf"), -float("inf")
top_view = {}
while queue:
for _ in range(len(queue)):
node, col = queue.popleft()
if node:
min_col, max_col = min(min_col, col), max(max_col, col)
if col not in top_view:
top_view[col] = node.data
queue.append((node.left, col - 1))
queue.append((node.right, col + 1))
return [top_view[i] for i in range(min_col, max_col + 1)]
Bottom View of Binary Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
def bottomView(self, root):
def dfs(node, level, col):
nonlocal min_col, max_col
if not node:
return
min_col, max_col = min(min_col, col), max(max_col, col)
if col not in bottom_view or level >= bottom_view[col][1]:
bottom_view[col] = node.data, level
dfs(node.left, level + 1, col - 1)
dfs(node.right, level + 1, col + 1)
min_col, max_col = float("inf"), -float("inf")
bottom_view = {}
dfs(root, 0, 0)
return [bottom_view[i][0] for i in range(min_col, max_col + 1)]
Analysis
- Python
def bottomView(self, root):
stack = [(root, 0, 0)]
min_col, max_col = float("inf"), -float("inf")
bottom_view = {}
while stack:
node, level, col = stack.pop()
if node:
min_col, max_col = min(min_col, col), max(max_col, col)
if col not in bottom_view or level >= bottom_view[col][1]:
bottom_view[col] = node.data, level
stack.append((node.right, level + 1, col + 1))
stack.append((node.left, level + 1, col - 1))
return [bottom_view[i][0] for i in range(min_col, max_col + 1)]
Analysis
- Python
def bottomView(self, root):
queue = collections.deque([(root, 0)])
min_col, max_col = float("inf"), -float("inf")
bottom_view = {}
while queue:
for _ in range(len(queue)):
node, col = queue.popleft()
if node:
min_col, max_col = min(min_col, col), max(max_col, col)
bottom_view[col] = node.data
queue.append((node.left, col - 1))
queue.append((node.right, col + 1))
return [bottom_view[i] for i in range(min_col, max_col + 1)]
545. Boundary of Binary Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
def setLeftBoundary(node):
if not node:
return
boundary.append(node.val) if not is_leaf(node) else None
setLeftBoundary(node.left)
setLeftBoundary(node.right) if not node.left else None
def setRightBoundary(node):
if not node:
return
setRightBoundary(node.right)
setRightBoundary(node.left) if not node.right else None
boundary.append(node.val) if not is_leaf(node) else None
def setLeaves(node):
if not node:
return
if is_leaf(node) and node != root:
boundary.append(node.val)
setLeaves(node.left)
setLeaves(node.right)
is_leaf = lambda node: not node.left and not node.right
boundary = [root.val]
setLeftBoundary(root.left)
setLeaves(root)
setRightBoundary(root.right)
return boundary
Analysis
- Python
def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
boundary = [root.val]
is_leaf = lambda node: not node.left and not node.right
# setLeftBoundary
stack = [root.left]
while stack:
node = stack.pop()
if node:
boundary.append(node.val) if not is_leaf(node) else None
stack.append(node.right) if not node.left else None
stack.append(node.left)
# setLeaves
stack = [root]
while stack:
node = stack.pop()
if node:
if is_leaf(node) and node != root:
boundary.append(node.val)
stack.append(node.right)
stack.append(node.left)
# setRightBoundary (post-order)
stack = [(root.right, False)]
while stack:
node, visited = stack.pop()
if node:
if visited:
boundary.append(node.val) if not is_leaf(node) else None
else:
stack.append((node, True))
stack.append((node.left, False)) if not node.right else None
stack.append((node.right, False))
return boundary