給定一個二叉樹
struct Node { int val; Node *left; Node *right; Node *next;}填充它的每個next指針，讓這個指針指向其下一個右側節點。如果找不到下一個右側節點，則將next指針設置為NULL。
初始狀態下，所有next指針都被設置為NULL。
進階：
你只能使用常量級額外空間。使用遞歸解題也符合要求，本題中遞歸程序佔用的棧空間不算做額外的空間複雜度。示例：
輸入：root = [1,2,3,4,5,null,7]輸出：[1,#,2,3,#,4,5,7,#]解釋：給定二叉樹如圖 A 所示，你的函數應該填充它的每個 next 指針，以指向其下一個右側節點，如圖 B 所示。提示：
樹中的節點數小於 6000-100 <= node.val <= 100來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/
Link：https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
寬度優先搜索O(N)
使用隊列上一題的代碼可以原封不動地放在這裡，哈哈~
from collections import dequeclass Solution: def connect(self, root: 'Node') -> 'Node':
if root is None: return None
queue = deque([root])
while len(queue) > 0: count = len(queue)
for i in range(count): cur = queue.popleft()
if i + 1 < count: cur.next = queue[0]
if cur.left is not None: queue.append(cur.left)
if cur.right is not None: queue.append(cur.right)
return root不使用隊列需要一個哨兵頭節點，不然代碼寫起來太麻煩了
有了頭節點，每一排當作鍊表連結起來
結尾記得把頭節點拆掉
class Solution: def connect(self, root: 'Node') -> 'Node':
node = root head = Node() while node is not None:
cur = head while node is not None: if node.left is not None: cur.next = node.left cur = cur.next
if node.right is not None: cur.next = node.right cur = cur.next
node = node.next
node = head.next head.next = None
return root單詞循環代碼
class Solution: def connect(self, root: 'Node') -> 'Node':
node = root cur = head = Node() while node is not None:
if node.left is not None: cur.next = node.left cur = cur.next
if node.right is not None: cur.next = node.right cur = cur.next
node = node.next
if node is None: cur = head node = head.next head.next = None
return root--End--