目錄

問題描述

解題過程

官方題解

---

問題描述

給定一個二叉樹：

struct Node {int val;Node *left;Node *right;Node *next;
}

填充它的每個 next 指針，讓這個指針指向其下一個右側節點。如果找不到下一個右側節點，則將 next 指針設置為?NULL?。

初始狀態下，所有?next 指針都被設置為?NULL?。

示例 1：

輸入：root = [1,2,3,4,5,null,7]
輸出：[1,#,2,3,#,4,5,7,#]
解釋：給定二叉樹如圖 A 所示，你的函數應該填充它的每個 next 指針，以指向其下一個右側節點，如圖 B 所示。序列化輸出按層序遍歷順序（由 next 指針連接），'#' 表示每層的末尾。

示例 2：

輸入：root = []
輸出：[]

提示：

• 樹中的節點數在范圍?[0, 6000]?內
• -100 <= Node.val <= 100

解題過程

樹的題目就是不會啊，直接學習解析吧，不掙扎了，橫向遍歷是一點思路都沒有

官方題解

方法一：層次遍歷

簡述一下deque()容器：deque是"double-end queue"的簡稱，是collections模塊中的，針對Python內置的容器，它類似于list，可以快速的在隊列頭部和尾部添加、刪除元素，是棧和隊列的一種廣義實現，常使用append()從右端加入元素，popleft()移除列表左端的一個元素。

需要注意的是，root本身屬于可迭代對象，所以在對queue賦值時，使用了[]，如上述代碼：

queue = deque([root])

首先得到根節點，最后通過循環獲得對應的下一級的所有節點，再確定next指向。