作者介紹：10年大廠數據\經營分析經驗，現任字節跳動數據部門負責人。
會一些的技術：數據分析、算法、SQL、大數據相關、python，歡迎探討交流
歡迎加入社區：碼上找工作
作者專欄每日更新：
LeetCode解鎖1000題: 打怪升級之旅
python數據分析可視化：企業實戰案例
漫畫版算法詳解
python源碼解讀
程序員必備的數學知識與應用
題目描述
給定一個完美二叉樹，其所有葉子節點都在同一層，每個父節點都有兩個子節點。二叉樹的定義如下：
class Node:def __init__(self, val=0, left=None, right=None, next=None):self.val = valself.left = leftself.right = rightself.next = next
填充它的每個 next 指針，讓這個指針指向其下一個右側節點。如果找不到下一個右側節點，則將 next 指針設置為 None。
初始狀態下，所有 next 指針都被設置為 None。
方法一：層序遍歷（BFS）
解題步驟：
- 使用隊列進行層序遍歷。
- 對于每一層的節點，通過隊列的長度來確定節點的數量。
- 遍歷當前層的節點，將每個節點的
next指向隊列中的下一個節點。 - 最后一個節點的
next指向None。
Python 代碼示例
from collections import dequedef connect(root):"""使用層序遍歷來填充每個節點的下一個右側節點指針。參數:root (Node): 完美二叉樹的根節點。返回:Node: 修改后的樹的根節點。"""# 如果根節點為空，則直接返回Noneif not root:return None# 初始化隊列，并將根節點加入隊列queue = deque([root])# 當隊列不為空時，進行層序遍歷while queue:# 獲取當前層的節點數量size = len(queue)# 遍歷當前層的每個節點for i in range(size):# 從隊列中取出一個節點node = queue.popleft()# 如果不是當前層的最后一個節點，將當前節點的next指向隊列中的下一個節點if i < size - 1:node.next = queue[0]# 如果當前節點有左子節點，將左子節點加入隊列if node.left:queue.append(node.left)# 如果當前節點有右子節點，將右子節點加入隊列if node.right:queue.append(node.right)# 返回根節點return root方法一利用層序遍歷（BFS）來填充每個節點的下一個右側節點指針，下面通過 ASCII 圖形來說明這個方法的工作過程。
考慮一個完美二叉樹如下所示：
1/ \2 3/ \ / \4 5 6 7
算法圖解
我們使用隊列來按層級遍歷這棵樹，并設置每個節點的 next 指針。以下是各個步驟的圖解說明：
初始狀態
- 初始化隊列以包含根節點。
隊列: [1]
第一層處理
- 取出節點 1，發現它有左右子節點 2 和 3，將這兩個節點加入隊列。
隊列: [2, 3]
next指針連接: 1 -> None
- 設置節點 1 的
next指向None（因為它是第一層的唯一節點）。
第二層處理
- 取出節點 2，由于它不是隊列中的最后一個節點，設置
next指向隊列中的下一個節點（節點 3）。同時將節點 2 的子節點 4 和 5 加入隊列。
隊列: [3, 4, 5]
next指針連接: 2 -> 3
- 取出節點 3，設置
next指向None（因為它是當前層的最后一個節點），將節點 3 的子節點 6 和 7 加入隊列。
隊列: [4, 5, 6, 7]
next指針連接: 3 -> None
第三層處理
- 處理節點 4, 5, 6, 7 類似，按順序設置
next指針：
隊列: [5, 6, 7]
next指針連接: 4 -> 5
隊列: [6, 7]
next指針連接: 5 -> 6
隊列: [7]
next指針連接: 6 -> 7
隊列: []
next指針連接: 7 -> None
在每一步中，我們從隊列中移除一個節點，如果該節點不是當前層的最后一個節點，則將其 next 指針設置指向隊列中的下一個節點。這樣，每一層的節點都通過 next 指針連成一條鏈。當處理完當前層的所有節點后，隊列中就包含了下一層的所有節點，重復以上步驟直到隊列為空。這樣的遍歷確保了每個節點的 next 指針正確地指向了其右側的節點。
方法二：使用已建立的 next 指針
解題步驟：
- 從根節點開始，利用上一層的
next指針來遍歷和鏈接當前層的節點。 - 對于每個節點，鏈接其左子節點到右子節點，右子節點到下一個節點的左子節點（如果存在）。
Python 代碼示例
def connect(root):"""利用已建立的 next 指針來填充每個節點的下一個右側節點指針。參數:root (Node): 完美二叉樹的根節點。返回:Node: 修改后的樹的根節點。"""# 如果根節點為空，則直接返回Noneif not root:return None# 初始化leftmost指針，這個指針始終指向每一層的最左側節點leftmost = root# 當左側節點存在時，繼續處理下一層while leftmost.left:# 使用head指針遍歷當前層的節點，head初始指向當前層的最左側節點head = leftmostwhile head:# 將當前節點的左子節點的next指向右子節點head.left.next = head.right# 如果當前節點的next不為空，將右子節點的next指向當前節點next的左子節點if head.next:head.right.next = head.next.left# 移動到當前層的下一個節點head = head.next# 移動到下一層的最左側節點leftmost = leftmost.left# 返回根節點return root方法三：遞歸法
解題步驟：
- 遞歸地連接每個節點的左子節點到其右子節點。
- 連接相鄰子樹的右子節點到左子節點。
Python 代碼示例
def connect(root):if not root or not root.left:return rootroot.left.next = root.rightif root.next:root.right.next = root.next.leftconnect(root.left)connect(root.right)return root
方法四：使用額外的節點追蹤下一層的開始
解題步驟：
- 使用一個額外的節點
dummy來追蹤每一層的開始。 - 通過一個循環連接同一層的所有節點。
Python 代碼示例
def connect(root):if not root:return Nonecurrent = rootwhile current:dummy = Node(0)tail = dummywhile current:if current.left:tail.next = current.lefttail = tail.nextif current.right:tail.next = current.righttail = tail.nextcurrent = current.nextcurrent = dummy.nextreturn root
方法五：迭代優化
解題步驟：
- 類似于方法二，但使用迭代而非遞歸。
- 遍歷每一層，連接相應的節點。
Python 代碼示例
def connect(root):if not root:return Nonenode = rootwhile node and node.left:next_level = node.leftwhile node:node.left.next = node.rightnode.right.next =node.next.left if node.next else Nonenode = node.nextnode = next_levelreturn root
算法分析
- 時間復雜度：所有方法都需要遍歷每個節點，因此時間復雜度為 O(N)，其中 N 是樹中的節點數。
- 空間復雜度：
- 方法一：O(N)，需要額外的隊列。
- 方法二至五：O(1)，只使用常數額外空間。
不同算法的優劣勢對比
- 層序遍歷（方法一）直觀且易于理解，但需要額外的空間來存儲隊列。
- 使用已建立的 next 指針（方法二）是空間復雜度最優的解法，適合空間敏感的應用。
- 遞歸法（方法三）代碼簡潔，但在非尾遞歸的編譯器上可能導致棧溢出。
- 使用額外節點（方法四）適合不熟悉指針操作的場景。
- 迭代優化（方法五）提供了一個折中的解決方案，空間復雜度低，且較易于理解。
應用示例
這些方法可以用在需要層級遍歷但希望節約空間的場景，如實時數據處理、游戲編程中的場景管理，或任何需要快速訪問同一層級節點的數據結構設計中。
