BFS vs DFS 演算法簡單說明

BFS (Breadth First Search): 廣度優先搜尋

利用 queue 的方式走訪圖形(Graph) 的點，概念會先將 root 放入 queue 中，接著使用 while 去遍歷 queue 並且在遍歷的過程中分別放入左節點以及右節點至 queue 中

樹的節點 class 如下:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
c1l = TreeNode(5)
c1r = TreeNode(6)
c2l = TreeNode(7)
c2r = TreeNode(8)
c1 = TreeNode(val=2, left=c1l, right=c1r)
c2 = TreeNode(val=2, left=c2l, right=c2r)
r = TreeNode(val=1, left=c1, right=c2)

實作 BFS:

def bfs(node):
    result = []
    queue = [node]

    while len(queue):
        curr = queue.pop(0)
        result.append(curr.val)
        if curr.left:
            queue.append(curr.left)
        if curr.right:
            queue.append(curr.right)
    return result

DFS(Depth First Search): 深度優先搜尋

跟 BFS 類似的概念，只是從 queue 改為使用 stack。因為使用 stack LIFO 的特性，所以先探察左邊子樹或者右邊子樹會影響執行的順序，例如：假如 DFS 想先從右邊開始的話，則程式需先 push 左子樹後在 push 右子樹

實作 DFS:

def bfs(node):
    result = []
    stack = [node]

    while len(stack):
        curr = stack.pop()
        result.append(curr.val)
        if curr.left:
            stack.append(curr.left)
        if curr.right:
            stack.append(curr.right)
    return result

print(bfs(r))

參考資源:

[BinaryTree] 廣度搜尋BFS vs 深度搜尋DFS