我試圖解決二叉樹級別順序遍歷問題 - LeetCode給定一棵二叉樹，返回其節點值的層序遍歷。（即從左到右，一層一層）。例如：給定二叉樹[3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7返回其層序遍歷為：[ [3], [9,20], [15,7]]我的方案很直觀，BFS遍歷收集每一層的值from collections import dequeclass Solution: def levelOrder(self, root): if not root: return [] #base case res = [] #queue to colloct all the nodes queue = deque([root]) while queue: level_vals = [] #hold the values at the current level. for _ in range(len(queue)): #evalute once before execution enter the loop cur = queue.popleft() if node.left: queue.append(cur.left) if node.right: queue.append(cur.right) level_vals.append(cur.val) res.append(level_vals) return res 我在討論區閱讀了這樣的 bfs 和隊列解決方案# BFS + dequedef levelOrder(self, root): res, queue = [], deque([(root, 0)]) while queue: cur, level = queue.popleft() if cur: if len(res) < level+1: res.append([]) res[level].append(cur.val) queue.append((cur.left, level+1)) queue.append((cur.right, level+1)) return res我對條件檢查感到困惑if len(res) < level+1: res.append([])，并認為它可以是 ' if cur: #if len(res) < level+1: res.append([]) res[level].append(cur.val) queue.append((cur.left, level+1)) queue.append((cur.right, level+1)) return res為什么需要條件檢查？
1 回答
慕無忌1623718
TA貢獻1744條經驗 獲得超4個贊
條件檢查在那里，以便res僅當在queue. 如果沒有檢查，代碼將一個新的空數組追加到res為每個節點遇到queue。
讓我們看看當您運行帶有條件檢查的代碼時會發生什么。對于您的示例樹，首先從隊列中彈出值為 3 的根節點。此時的長度res為0，level也是0。所以，len(res) > level + 1是真實的。因此，將附加一個新的空數組res來存儲樹級別 0 的值。處理級別 1 的第一個節點（值為 9）時的情況也是如此。但是，處理完之后，當我們開始處理級別 1 的第二個節點（值為 20）時，該res數組有 2 個元素（每個級別一個）并且級別的值為 1。len(res) > level + 1為 false 并且沒有插入任何內容res。
如果沒有那個檢查，在迭代結束時 res 數組將是這樣的：
[
[3],
[9, 20],
[15, 7],
[],
[]
]
請注意，因為您的樹中有 5 個節點，所以總共附加了 5 個數組，res但只有前 3 個被占用，因為您的樹有 3 個級別。
添加回答
舉報
0/150
提交
取消