Leetcode Binary Tree BFS解題心得
Leetcode Binary Tree BFS解題心得¶
在top interview 150 中基本題型是
讀取每一層layer by layer 然後做要求的事,可能是算平均,找最小/大,或是暫存
res, current = [], [root]while current: n = len(current) res.append(current[-1].val) for i in range(n): temp = current.pop(0) if temp.left: current.append(temp.left) if temp.right: current.append(temp.right)
基本格式如上,需要一個current去保存當下的node,
當curr裡面還有值的時候,先記錄當下的長度,即為該層的node數
接下來邊走訪邊pop,同時把left/right node保存進curr,即是記錄下一層的寬度,直到current為空,表示全部都走訪完畢
Comments
Loading comments…
Leave a Comment