BFS and DFS

BFS 和 DFS 為用以在 tree 中搜尋特定 node 的演算法

• Breadth-First Search 廣度優先搜尋
• Depth-First Search 深度優先搜尋

相關文章：Binary Tree 二元樹

Iterative Implementation

BFS：使用 Queue

Template

queue = collections.deque([root])
while queue: 
  curr = queue.popleft() 
  # ... some process about target

  for child in ... : # [curr.left, curr.right]: 
    if child: 
      queue.append(child)

DFS：使用 Stack

Template

stack = [root]
while stack:
  curr = stack.pop()
  # ... some process about target
      
  for child in ... : # [curr.left, curr.right]:
    if child:
      stack.append(child)

Recursive Implementation

❌ BFS

⭕️ DFS

Template

def recursive_dfs(curr, target):
  if curr is None:  
    return
        
  # ...
  for child in [curr.left, curr.right]:
    # ...
    subresult = recursive_dfs(child) 
    # ...

相關例題

• Leetcode # 1644. Lowest Common Ancestor of a Binary Tree II

相關例題

BFS

• Leetcode # 102. Binary Tree Level Order Traversal
• Leetcode # 103. Binary Tree Zigzag Level Order Traversal
• Leetcode # 490. The Maze
• Leetcode # 515. Find Largest Value in Each Tree Row
• Leetcode # 542. 01 Matrix
• Leetcode # 938. Range Sum of BST

DFS

• Leetcode # 98. Validate Binary Search Tree
• Leetcode # 111. Minimum Depth of Binary Tree
• Leetcode # 112. Path Sum
• Leetcode # 124. Binary Tree Maximum Path Sum
• Leetcode # 235. Lowest Common Ancestor of a Binary Search Tree
• Leetcode # 543. Diameter of Binary Tree
• Leetcode # 589. N-ary Tree Preorder Traversal
• Leetcode # 1110. Delete Nodes And Return Forest
• Leetcode # 1302. Deepest Leaves Sum
• Leetcode # 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
• Leetcode # 1644. Lowest Common Ancestor of a Binary Tree II

Last Updated on 2023/09/12 by A1go