116. 填充每個節點的下一個右側節點指標
Difficulty: 中等
給定一個 **完美二叉樹 **，其所有葉子節點都在同一層，每個父節點都有兩個子節點，二叉樹定義如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個 next 指標，讓這個指標指向其下一個右側節點，如果找不到下一個右側節點，則將 next 指標設定為 NULL，
初始狀態下，所有 next 指標都被設定為 NULL，
進階：
- 你只能使用常量級額外空間，
- 使用遞回解題也符合要求，本題中遞回程式占用的堆疊空間不算欄位外的空間復雜度，
示例：
輸入：root = [1,2,3,4,5,6,7]
輸出：[1,#,2,3,#,4,5,6,7,#]
解釋：給定二叉樹如圖 A 所示，你的函式應該填充它的每個 next 指標，以指向其下一個右側節點，如圖 B 所示，序列化的輸出按層序遍歷排列，同一層節點由 next 指標連接，'#' 標志著每一層的結束，
提示：
- 樹中節點的數量少于
4096 -1000 <= node.val <= 1000
Solution
Language: 全部題目
簡單來說，完美二叉樹的定義是任意一個父節點都有兩個子節點，題目的要求是填充每一個節點的右側next指標，然后我們可以把它轉化為求解二叉樹的層序遍歷，遍歷二叉樹每層的節點，然后把節點的next指標指向它的右側，注意初始狀態下，所有 next 指標都被設定為 NULL，所以不需要考慮每一層最后一個節點，
在實作層序遍歷（BFS）的程序中利用到了佇列的性質：先入先出，每次從佇列里pop出來的是該節點右側的節點，
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
?
class Solution:
def connect(self, root: 'Node') -> 'Node':
# BFS
if not root:
return
queue = [root]
while queue:
size = len(queue)
for i in range(size):
cur = queue.pop(0)
if i < size - 1: # 層序遍歷的最后一個元素不考慮
cur.next = queue[0]
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
return root
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/228519.html
標籤：其他