Binary tree BFS force buckle Python

102. Sequence traversal of binary tree

Their thinking ：
The sequence of sequence traversal is from top to bottom , Traverse from left to right .

From top to bottom, you traverse through the left and right subtrees of the root node .

From left to right, the number of nodes in each layer is recorded , Of level That's what it does , Double ended queues are used here for generalization , The following questions 103, z The shape loop records the nodes of each layer , It is also possible to use lists .

# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
# Add the root node 
queue = [root]
res = []
while queue:
# Nodes of each layer 
level = deque()
size = len(queue)
for _ in range(size):
cur = queue.pop(0)
level.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
if level:
res.append(list(level))
return res

103. Zigzag sequence traversal of binary tree

Their thinking ：
Define a flag As a record , Odd positive , Even numbers are reversed .

Double ended queues can easily add elements back and forth .

# 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 zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
# Add the root node 
queue = [root]
res = []
flag = True
while queue:
# Nodes of each layer 
level = deque() #deque
size = len(queue)
for _ in range(size):
cur = queue.pop(0)
if flag:
level.append(cur.val)
else:
level.appendleft(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
if level:
res.append(list(level))
flag = not flag
return res

107. Sequence traversal of binary tree II

Their thinking ：
As the title 102, This problem only reverses the node order of each layer of records .

Be careful. , I believe many people want to use reverse() Directly reverse the order of the list , But this function will not return the list after calling , Therefore, the order of nodes in each layer is reversed by slicing .

# 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 levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
# Add the root node 
queue = [root]
res = []
while queue:
# Nodes of each layer 
level = deque()
size = len(queue)
for _ in range(size):
cur = queue.pop(0)
level.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
if level:
res.append(list(level))
return res[::-1]

111. Minimum depth of binary tree

Their thinking ：
BFS Record the height of each layer , Then select the minimum depth .

# 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 minDepth(self, root: TreeNode) -> int:
if not root:
return 0
# Add the root node 
queue = [root]
depth = 1
while queue:
size = len(queue)
for _ in range(size):
cur = queue.pop(0)
if not cur.left and not cur.right:
return depth
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
depth += 1
return depth

DFS You can also solve this problem , Note as follows .

class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
left = self.minDepth(root.left)
right = self.minDepth(root.right)
if not root.left and not root.right: # No child node is a leaf node 
return 1
min_depth = 0xffffff
# Compare the left and right subtrees respectively , Select the number of nodes on the shortest path 
if root.left:
min_depth = min(left,min_depth)
if root.right:
min_depth = min(right, min_depth)
return min_depth + 1

another DFS How to write it , It's essentially the same thing ,
The advantage of listing an additional function is ,
Of internal functions base case It can be directly used to record the return value of empty nodes , For from
No additional variables are needed to store for comparison min_depth.

class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root: # Judge the root node 
return 0
def dfs(node):
if not node: # base case Record a value for comparison 
return float("inf")
elif not node.left and not node.right:
return 1
return min(dfs(node.left) , dfs(node.right)) + 1
return dfs(root)

BFS Algorithm and DFS One big difference between algorithms is ,BFS The first search result is the best , But space complexity is high .

DFS Time complexity is high , because DFS Only after exploring all nodes can we know which result is the best .