題目

題目連結

解題概念

此題簡單來說，就是要對一 Binary Tree 做 Level Order Traversal

對 Binary Tree 的各種 Travesal 不熟的朋友可以瀏覽此網頁
通常實際執行 Level Order Traversal 時，會使用 Graph 中的 BFS(Breadth-First Search; 廣度搜尋)
- Def :
  - 先選定一個頂點 A 開始走訪，逐一走過與頂點 A 相鄰未被走過的頂點
  - 若相鄰頂點都被走過，再從走訪過的頂點中擇一為新記錄點，逐一走過新記錄點相鄰未被走過的頂點，以此類推
    
    補充 : DFS 與 BFS 之差異
- 轉換成此題實際應用 :
  - 先選定樹根 Root 開始走訪，逐一走過 Root 的左右子點
  - 若Root 的左右子點都被走過，再從左右子點中擇一為新樹根，逐一走過新樹根的左右子點，以此類推
此次解題，我是用非遞迴的方式去解，但在 Discussion 中也有看到遞迴的方式，故以下都會提到

實際寫Code

目標函式 : levelOrder(root)

節點格式 :

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Input : root : TreeNode
Output : List[List[int]]

非遞迴寫法

前置作業 :

result = [] # 結果陣列

start_round = [] # 每回合之目標節點陣列

if root is None : # 若 root 為空，則回傳空陣列
    return start_round

start_round.append(root) # 將 Root 先置入 start_round 中

使用雙層 while 迴圈 :
1. 針對每一層
2. 針對該層的每一節點

程式碼 :

# lst 迴圈 : 針對每一層
while len(start_round) != 0 :
    
    next_round = [] # 暫存下一層之節點

    # 2nd 迴圈 : 針對單一層的每個節點
    temp_result = [] # 暫存這一層的所有節點值
    while len(start_round) != 0 :

        temp = start_round.pop(0) # 取出該層一節點 temp
        
        temp_result.append(temp.val) # 將該節點的值置入 temp_result

        # 若該節點有左子點，則將該子點放入 next_round 中
        if temp.left is not None :
            next_round.append(temp.left)

        # 若該節點有右子點，則將該子點放入 next_round 中
        if temp.right is not None :
            next_round.append(temp.right)

        result.append(temp_result) # 將此回合結果放入 result 中 

        start_round = next_round # 將下回合的節點放入 start_round 中，為下回合做準備

遞迴寫法

前置作業 :

result = [] # 結果陣列

start_round = [] # 每回合之目標節點陣列

if root is None : # 若 root 為空，則回傳空陣列
    return start_round

start_round.append(root) # 將 Root 先置入 start_round 中

# def BFS(...) : 
    # ...

BFS(queue)
return result

使用 BFS() 函數遞迴 : 每一次呼叫，都代表對一層 Binary Tree 做計算

程式碼 :

def BFS(target):

    # 若目標陣列沒元素，就停止向下遞迴
    if len(target) == 0 :
        return
    
    next_round = [] # 暫存下一層之節點
    temp_result = [] # 暫存這一層的所有節點值

    for item in target : # 針對這層的所有節點

        temp_result.append(item.val) # 將該節點的值置入 temp_result

        # 若該節點有左子點，則將該子點放入 next_round 中
        if item.left is not None :
            next_round.append(item.left)

        # 若該節點有右子點，則將該子點放入 next_round 中
        if item.right is not None :
            next_round.append(item.right)

        result.append(temp_result) # 將此回合結果放入 result 中 
        BFS(next_queue) # 開始下一回合

【Leetcode解題】102. Binary Tree Level Order Traversal

題目

解題概念

實際寫Code

非遞迴寫法

遞迴寫法

參考資料