Binary Tree BFS¶
Table of Contents¶
- 102. Binary Tree Level Order Traversal (Medium)
- 103. Binary Tree Zigzag Level Order Traversal (Medium)
- 107. Binary Tree Level Order Traversal II (Medium)
- 199. Binary Tree Right Side View (Medium)
- 513. Find Bottom Left Tree Value (Medium)
- 515. Find Largest Value in Each Tree Row (Medium)
- 637. Average of Levels in Binary Tree (Easy)
- 1161. Maximum Level Sum of a Binary Tree (Medium)
- 993. Cousins in Binary Tree (Easy)
- 2583. Kth Largest Sum in a Binary Tree (Medium)
- 1302. Deepest Leaves Sum (Medium)
- 2415. Reverse Odd Levels of Binary Tree (Medium)
- 1609. Even Odd Tree (Medium)
- 623. Add One Row to Tree (Medium)
- 2471. Minimum Number of Operations to Sort a Binary Tree by Level (Medium)
- 863. All Nodes Distance K in Binary Tree (Medium)
- 2641. Cousins in Binary Tree II (Medium)
- 919. Complete Binary Tree Inserter (Medium)
- 331. Verify Preorder Serialization of a Binary Tree (Medium)
- 958. Check Completeness of a Binary Tree (Medium)
- 662. Maximum Width of Binary Tree (Medium)
- 3157. Find the Level of Tree with Minimum Sum (Medium) 👑
- 1602. Find Nearest Right Node in Binary Tree (Medium) 👑
- 742. Closest Leaf in a Binary Tree (Medium) 👑
- 1660. Correct a Binary Tree (Medium) 👑
102. Binary Tree Level Order Traversal¶
from collections import deque
from typing import List, Optional
from binarytree import Node as TreeNode
from binarytree import build
def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
q = deque([root])
res = []
while q:
level = []
size = len(q)
for _ in range(size):
cur = q.popleft()
level.append(cur.val)
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
res.append(level)
return res
tree = build([3, 9, 20, None, None, 15, 7])
print(tree)
# 3___
# / \
# 9 _20
# / \
# 15 7
print(levelOrder(tree)) # [[3], [9, 20], [15, 7]]
103. Binary Tree Zigzag Level Order Traversal¶
from collections import deque
from typing import List, Optional
from binarytree import Node as TreeNode
from binarytree import build
def zigzagLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
q = deque([root])
res = []
while q:
level = []
size = len(q)
for _ in range(size):
cur = q.popleft()
level.append(cur.val)
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
res.append(level if not len(res) % 2 else level[::-1])
return res
if __name__ == "__main__":
tree = build([3, 9, 20, None, None, 15, 7])
print(tree)
# 3___
# / \
# 9 _20
# / \
# 15 7
assert zigzagLevelOrder(tree) == [[3], [20, 9], [15, 7]]
107. Binary Tree Level Order Traversal II¶
from collections import deque
from typing import List, Optional
from binarytree import Node as TreeNode
from binarytree import build
def levelOrderBottom(root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
res = []
q = deque([root])
while q:
level = []
n = len(q)
for _ in range(n):
cur = q.popleft()
level.append(cur.val)
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
res.append(level)
return res[::-1]
tree = build([3, 9, 20, None, None, 15, 7])
print(tree)
# 3___
# / \
# 9 _20
# / \
# 15 7
print(levelOrderBottom(tree)) # [[15, 7], [9, 20], [3]]
199. Binary Tree Right Side View¶
from collections import deque
from typing import List, Optional
from binarytree import Node as TreeNode
from binarytree import build
# Binary Tree BFS
def rightSideViewBFS(root: Optional[TreeNode]) -> List[int]:
if not root:
return []
q = deque([root])
res = []
while q:
n = len(q)
for i in range(n):
node = q.popleft()
if i == n - 1:
res.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return res
# Binary Tree DFS
def rightSideViewDFS(root: Optional[TreeNode]) -> List[int]:
"""后序遍历，先右后左，遇到的第一个节点就是该深度的最右侧节点"""
ans = []
def dfs(node, depth):
if node is None:
return
if depth == len(ans): # 这个深度首次遇到
ans.append(node.val)
dfs(node.right, depth + 1)
dfs(node.left, depth + 1)
dfs(root, 0)
return ans
if __name__ == "__main__":
root = [1, 2, 2, 3, 4, None, 3, None, None, 5]
root = build(root)
print(root)
# ____1
# / \
# 2__ 2
# / \ \
# 3 4 3
# /
# 5
assert rightSideViewBFS(root) == [1, 2, 3, 5]
assert rightSideViewDFS(root) == [1, 2, 3, 5]
513. Find Bottom Left Tree Value¶
from collections import deque
from typing import Optional
from binarytree import build
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def findBottomLeftValue(root: Optional[TreeNode]) -> int:
if not root:
return 0
queue = deque([root])
result = 0
while queue:
size = len(queue)
for i in range(size):
node = queue.popleft()
if i == 0:
result = node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
root = [1, 2, 2, 3, 4, None, None, None, None, 5]
root = build(root)
print(root)
# ____1
# / \
# 2__ 2
# / \
# 3 4
# /
# 5
print(findBottomLeftValue(root)) # 5
515. Find Largest Value in Each Tree Row¶
from collections import deque
from typing import List, Optional
from binarytree import build
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def largestValues(root: Optional[TreeNode]) -> List[int]:
if not root:
return []
queue = deque([root])
result = []
while queue:
levelMax = float("-inf")
for _ in range(len(queue)):
node = queue.popleft()
levelMax = max(levelMax, node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(levelMax)
return result
root = [1, 2, 2, 3, 4, None, None, None, None, 5]
root = build(root)
print(root)
# ____1
# / \
# 2__ 2
# / \
# 3 4
# /
# 5
print(largestValues(root)) # [1, 2, 4, 5]
637. Average of Levels in Binary Tree¶
from collections import deque
from typing import List, Optional
from binarytree import Node as TreeNode
from binarytree import build
# Binary Tree BFS
def averageOfLevels(root: Optional[TreeNode]) -> List[float]:
if not root:
return []
q = deque([root])
res = []
while q:
n = len(q)
level = 0
for _ in range(n):
cur = q.popleft()
level += cur.val
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
res.append(float(level / n))
return res
if __name__ == "__main__":
root = [3, 9, 20, None, None, 15, 7]
root = build(root)
print(root)
# 3___
# / \
# 9 _20
# / \
# 15 7
assert averageOfLevels(root) == [3.00000, 14.50000, 11.00000]
1161. Maximum Level Sum of a Binary Tree¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# BFS
def maxLevelSum(root: Optional[TreeNode]) -> int:
if not root:
return 0
q = deque([root])
res = 0
maxSum = float("-inf")
level = 1
while q:
n = len(q)
curSum = 0
for _ in range(n):
node = q.popleft()
curSum += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if curSum > maxSum:
maxSum = curSum
res = level
level += 1
return res
root = [1, 7, 0, 7, -8, None, None]
root = build(root)
print(root)
# ___1
# / \
# 7 0
# / \
# 7 -8
print(maxLevelSum(root)) # 2
993. Cousins in Binary Tree¶
from collections import deque
from math import inf
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
def is_cousins_bfs(root: Optional[TreeNode], x: int, y: int) -> bool:
if not root:
return False
q = deque([(root, inf)])
while q:
size = len(q)
p1, p2 = None, None
for _ in range(size):
cur, par = q.popleft()
val = cur.val
if x == val:
p1 = par
if y == val:
p2 = par
if cur.left:
q.append((cur.left, val))
if cur.right:
q.append((cur.right, val))
# Check if both found at same level
if p1 and p2:
return p1 != p2 # Same level, different parents
elif p1 or p2:
return False # Only one found at this level
return False
if __name__ == "__main__":
root = build([1, 2, 3, None, 4, None, 5])
assert is_cousins_bfs(root, 5, 4)
root = build([1, 2, 3, None, 4])
assert not is_cousins_bfs(root, 2, 3)
root = build([1, 2, 3, 4])
assert not is_cousins_bfs(root, 4, 3)
2583. Kth Largest Sum in a Binary Tree¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# BFS
def kthLargestLevelSum(root: Optional[TreeNode], k: int) -> int:
if not root:
return 0
sums = []
q = deque([root])
while q:
size = len(q)
level = 0
for _ in range(size):
node = q.popleft()
level += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
sums.append(level)
if len(sums) < k:
return -1
sums.sort()
return sums[-k]
root = [5, 8, 9, 2, 1, 3, 7, 4, 6]
root = build(root)
k = 2
print(kthLargestLevelSum(root, k)) # 13
1302. Deepest Leaves Sum¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# BFS
def deepestLeavesSum(root: Optional[TreeNode]) -> int:
if not root:
return 0
q = deque([root])
while q:
n = len(q)
res = 0
for _ in range(n):
node = q.popleft()
res += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return res
root = [1, 2, 3, 4, 5, None, 6, 7, None, None, None, None, None, 8]
root = build(root)
print(root)
# __1
# / \
# 2 3__
# / \ \
# 4 5 6
# / /
# 7 8
print(deepestLeavesSum(root)) # 15
2415. Reverse Odd Levels of Binary Tree¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
def reverseOddLevels(root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
q = deque([root])
level = -1
while q:
size = len(q)
nodes = []
level += 1
for _ in range(size):
node = q.popleft()
nodes.append(node)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if level % 2 == 1:
i, j = 0, len(nodes) - 1
while i < j:
nodes[i].val, nodes[j].val = nodes[j].val, nodes[i].val
i += 1
j -= 1
return root
if __name__ == "__main__":
root = build([2, 3, 5, 8, 13, 21, 34])
print(root)
# ___2___
# / \
# 3 _5
# / \ / \
# 8 13 21 34
print(reverseOddLevels(root))
# ___2___
# / \
# 5 _3
# / \ / \
# 8 13 21 34
1609. Even Odd Tree¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
def isEvenOddTree(root: Optional[TreeNode]) -> bool:
if not root:
return True
q = deque([root])
level = 0
while q:
size = len(q)
prev = None
for _ in range(size):
node = q.popleft()
if level % 2 == 0:
if node.val % 2 == 0:
return False
if prev and node.val <= prev:
return False
else:
if node.val % 2 == 1:
return False
if prev and node.val >= prev:
return False
prev = node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
level += 1
return True
if __name__ == "__main__":
root = build([5, 4, 2, 3, 3, 7])
print(root)
# __5__
# / \
# 4 2
# / \ /
# 3 3 7
assert isEvenOddTree(root) is False
623. Add One Row to Tree¶
from collections import deque
from copy import deepcopy
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# BFS
def addOneRow_bfs(
root: Optional[TreeNode], val: int, depth: int
) -> Optional[TreeNode]:
if not root:
return None
if depth == 1:
new = TreeNode(val)
new.left = root
return new
q = deque([root])
cur = 1
while q:
size = len(q)
for _ in range(size):
node = q.popleft()
if cur == depth - 1:
old_left, old_right = node.left, node.right
node.left, node.right = TreeNode(val), TreeNode(val)
node.left.left = old_left
node.right.right = old_right
else:
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
cur += 1
return root
# DFS
def addOneRow_dfs(
root: Optional[TreeNode], val: int, depth: int
) -> Optional[TreeNode]:
if depth == 1:
new = TreeNode(val)
new.left = root
return new
def dfs(node, cur):
if not node:
return
if cur == depth - 1:
old_left, old_right = node.left, node.right
node.left = TreeNode(val, old_left, None)
node.right = TreeNode(val, None, old_right)
else:
dfs(node.left, cur + 1)
dfs(node.right, cur + 1)
dfs(root, 1)
return root
if __name__ == "__main__":
root = build([4, 2, 6, 3, 1, 5])
print(root)
# __4__
# / \
# 2 6
# / \ /
# 3 1 5
print(addOneRow_bfs(deepcopy(root), 1, 2))
# 4
# / \
# __1 1__
# / \
# 2 6
# / \ /
# 3 1 5
print(addOneRow_dfs(deepcopy(root), 1, 2))
# 4
# / \
# __1 1__
# / \
# 2 6
# / \ /
# 3 1 5
2471. Minimum Number of Operations to Sort a Binary Tree by Level¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
def _min_swaps_to_sort(nums):
"""
Calculate the minimum number of swaps to sort the array.
Method: Permutation Cycle
"""
n = len(nums)
arr = [(num, i) for i, num in enumerate(nums)]
arr.sort(key=lambda x: x[0])
visited = [False] * n
res = 0
for i in range(n):
if visited[i] or arr[i][1] == i:
continue
cycle_len = 0
j = i
while not visited[j]:
visited[j] = True
j = arr[j][1]
cycle_len += 1
if cycle_len > 1:
res += cycle_len - 1
return res
def minimumOperations_bfs(root: Optional[TreeNode]) -> int:
if not root:
return 0
res = 0
q = deque([root])
while q:
size = len(q)
level = []
for _ in range(size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res += _min_swaps_to_sort(level)
return res
if __name__ == "__main__":
root = build([1, 4, 3, 7, 6, 8, 5, None, None, None, None, 9, None, 10])
print(root)
# __1____
# / \
# 4 3___
# / \ / \
# 7 6 8 _5
# / /
# 9 10
assert minimumOperations_bfs(root) == 3
863. All Nodes Distance K in Binary Tree¶
from collections import deque
from typing import List
from binarytree import Node as TreeNode
from binarytree import build
# BFS
def distanceK(root: TreeNode, target: TreeNode, k: int) -> List[int]:
parent = dict()
def dfs(node, par=None):
if node:
parent[node] = par
dfs(node.left, node)
dfs(node.right, node)
dfs(root)
q = deque([(target, 0)])
seen = set([target])
while q:
node, dist = q.popleft()
if dist == k:
return [node.val] + [node.val for node, _ in q]
for nei in (node.left, node.right, parent[node]):
if nei and nei not in seen:
seen.add(nei)
q.append((nei, dist + 1))
return []
root = build([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
print(root)
# ______3__
# / \
# 5__ 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
target = root.left
k = 2
print(distanceK(root, target, k)) # [7, 4, 1]