文章目錄
- 1. 題目
- 1.1 示例
- 1.2 說明
- 1.3 限制
- 1.4 進階
- 2. 解法一（廣度優先遍歷）
- 2.1 分析
- 2.2 解答
- 2.3 復雜度
1. 題目
給定一棵完美二叉樹，即該二叉樹的所有葉子結點都在同一層且每一個父結點都有兩個子結點，二叉樹的結點定義如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
請你填充每個 next 指標，使得該指標指向該結點右邊第一個同層結點，如果當前結點右邊無結點，請將 next 指標設為 null ，
初始狀態下每一個 next 指標都是 null ，
1.1 示例
-
示例 1 1 1：
-
輸入：
root = [1, 2, 3, 4, 5, 6, 7] -
輸出：
[1, #, 2, 3, #, 4, 5, 6, 7, #] -
說明： 給定如下圖 A 所示的完美二叉樹，你的解答應該給出如圖 B 所示的結果，序列化的輸出按層序遍歷（即廣度優先遍歷）排列，同一層節點由
next指標連接，'#'標志著每一層的結束，
1.2 說明
- 來源： 力扣（LeetCode）
- 鏈接： https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node
1.3 限制
-1000 <= Node.val <= 1000；- 二叉樹的結點總數范圍為 [ 0 , 2 12 ? 1 ] [0,\textit{ }2^{12} - 1] [0, 212?1] ，
1.4 進階
- 你只能使用常量級額外空間，
- 使用遞回解題也符合要求，本題中遞回程式占用的堆疊空間不算欄位外的空間復雜度，
2. 解法一（廣度優先遍歷）
2.1 分析
由示例很明顯可以看出來每一層的結點之間按照廣度優先遍歷的順序通過 next 指標進行了連接，
2.2 解答
from collections import deque
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:
if root is None:
return
visiting = deque([root])
while len(visiting) > 0:
if len(visiting) == 1:
node = visiting.popleft()
if node.left:
visiting.append(node.left)
if node.right:
visiting.append(node.right)
continue
for i in range(len(visiting) - 1):
visiting[i].next = visiting[i + 1]
for i in range(len(visiting)):
node = visiting.popleft()
if node.left:
visiting.append(node.left)
if node.right:
visiting.append(node.right)
return root
實際上，上述解答的核心代碼沒有能夠包含雙端佇列 visiting 中僅有根結點的情況，下面是對此的優化：
from collections import deque
from typing import Optional
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) -> Optional[Node]:
if root is None:
return
visiting = deque([root])
while len(visiting) > 0:
node = visiting[0]
for i in range(1, len(visiting)):
node.next = visiting[i]
node = visiting[i]
for i in range(len(visiting)):
node = visiting.popleft()
if node.left:
visiting.append(node.left)
if node.right:
visiting.append(node.right)
return root
更進一步地，即使是上述實作，也需要使用兩次的回圈遍歷，一次是對每一層結點的 next 指標進行填充，另一次是將當前層結點的子結點加入雙端佇列，下面給出繼續優化的代碼：
from collections import deque
from typing import Optional
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) -> Optional[Node]:
if not root:
return root
visiting = deque([root])
while visiting:
size = len(visiting)
for i in range(size):
node = visiting.popleft()
if i < size - 1:
node.next = visiting[0]
if node.left:
visiting.append(node.left)
if node.right:
visiting.append(node.right)
return root
- 執行用時： 52 ms , 在所有 Python3 提交中擊敗了 91.57% 的用戶；
- 記憶體消耗： 16.5 MB , 在所有 Python3 提交中擊敗了 86.35% 的用戶，
實際上，從上述的優化代碼可以得出一個編程的原則：即在使用 for 回圈時，盡量避免將回圈結束的條件變數化，例如這里使用 size 而非 len(visiting) 來指示 for 回圈的結束，否則當 visiting 中的元素變化時， for 回圈結束的條件會改變，進而可能導致意料之外的情況，
2.3 復雜度
- 時間復雜度： O ( n ) O(n) O(n) ，
- 空間復雜度： O ( n ) O(n) O(n)，這是一棵完美二叉樹，它的最后一個層級包含的節點數量為總結點個數的一半，此時占用的輔助雙端佇列容量最大，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/347073.html
標籤：其他
上一篇：每日一題:42. 接雨水
下一篇：語意分割（研究現狀、技識訓礎）