目錄
100. 相同的樹
103. 二叉樹的鋸齒形層次周遊
107. 二叉樹的層次周遊 II
111. 二叉樹的最小深度
112. 路徑總和 II
129. 求根到葉子節點數字之和
199. 二叉樹的右視圖
222. 完全二叉樹的節點個數
257. 二叉樹的所有路徑
404. 左葉子之和
100. 相同的樹
1. 題目要求
2. 解決過程
樹節點定義
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
個人實作
法一：暴力法。分别周遊兩棵樹所有節點，并記錄在隊列或清單等容器中，最後直接對比異同。由于太過直白且低效，此處不作實作。空間複雜度 O(m+n)，時間複雜度 O(n)。
法二：遞歸 (DFS - preorder traversal)。同步周遊兩棵樹相應節點，一旦發現不同直接傳回 False，否則不斷遞歸直至完成所有節點比較。最終各結果使用邏輯運算符 and 綜合。空間複雜度 O(n)，時間複雜度 O(n)。
2020/08/02 - 89.18% (36ms) - 利索
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if (not p) and (not q):
return True
if (not p) or (not q) or (p.val != q.val):
return False
else:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
法三：疊代 (BFS)。通過廣度優先周遊，按順序逐層逐個對比各節點。空間複雜度約 O(n)，時間複雜度 O(n)。
2020/08/02 - 96.85% (32ms) - 很好
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
# 建立 BFS 輔助隊列 (隻使用一個隊列也行, 每對元素使用元組收集, 如 (p, q))
P = collections.deque() # 樹 P 輔助隊列
P.append(p)
Q = collections.deque() # 樹 Q 輔助隊列
Q.append(q)
# 隻要隊列還有元素就一直判斷
while P and Q:
cur_p = P.popleft()
cur_q = Q.popleft()
# 空節點跳過
if (not cur_p) and (not cur_q):
continue
# 父節點值對比(任一為空或值不相同則樹不同)
if (not cur_p) or (not cur_q) or (cur_p.val != cur_q.val):
return False
# 左孩子節點入隊
P.append(cur_p.left)
Q.append(cur_q.left)
# 右孩子節點入隊
P.append(cur_p.right)
Q.append(cur_q.right)
return True
官方實作與說明
# 同個人實作法二
class Solution:
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
# p and q are both None
if not p and not q:
return True
# one of p and q is None
if not q or not p:
return False
if p.val != q.val:
return False
return self.isSameTree(p.right, q.right) and self.isSameTree(p.left, q.left)
# 同個人實作法三
from collections import deque
class Solution:
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
def check(p, q):
# if both are None
if not p and not q:
return True
# one of p and q is None
if not q or not p:
return False
if p.val != q.val:
return False
return True
deq = deque([(p, q),]) # 似乎隻使用一個輔助隊列更簡潔些？
while deq:
p, q = deq.popleft()
if not check(p, q):
return False
if p:
deq.append((p.left, q.left))
deq.append((p.right, q.right))
return True
參考文獻
https://leetcode-cn.com/problems/same-tree/submissions/
https://leetcode-cn.com/problems/same-tree/solution/xiang-tong-de-shu-by-leetcode/
103. 二叉樹的鋸齒形層次周遊
1. 題目要求
2. 解決過程
樹節點定義
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
個人實作
法一：BFS 改。使用 棧 (Stack) 取代經典 BFS 所使用的 隊列 (Queue) 可實作題求的 鋸齒形層次周遊 —— 水準鏡像翻轉 S 型層序周遊。即層次周遊順序由原先的 每層從左往右，變換為 先從左往右、再從右往左、後從左往右 ... 交替進行。以下實作十分直覺，要點即注意子節點添加順序應符合邏輯。空間複雜度 O(m) (m 是最大層節點數)，時間複雜度 O(n)。
注意，若使用 雙端隊列 (Deque) 也可以模拟 棧 (Stack) 的 先進後出 性質，令入隊和出隊位置在同一端 即可。
2020/08/03 - 79.03% (40ms)
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
# 使用 python.list 替代 pythonds.basic.stack 作為棧
# 使用 collections.deuqe 在同一端入隊出隊也可以 (FILO)
L = [] # 從左起始, 往右周遊
R = [] # 從右起始, 往左周遊
L.append(root) # 根節點先入 L
result = [] # 結果清單
# 水準鏡像 S 型層序周遊
while L or R:
temp = [] # 目前層清單
# 從左往右周遊
if L:
while L:
cur = L.pop() # 目前層節點從左往右出棧
temp.append(cur.val) # 記錄
# 下一層節點從左往右入棧
if cur.left:
R.append(cur.left)
if cur.right:
R.append(cur.right)
# 從右往左周遊
else:
while R:
cur = R.pop() # 目前層節點從右往左出棧
temp.append(cur.val) # 記錄
# 下一層節點從右往左入棧
if cur.right:
L.append(cur.right)
if cur.left:
L.append(cur.left)
# 目前層周遊結果
result.append(temp) # 記錄
return result
此外，若仍堅持使用經典 BFS，則可能需要 每隔一層令層周遊結果先反轉 (temp = temp[::-1]*) 再添加到結果清單中 (result.append(temp))。由于清單切片反轉的複雜度為 O(m)，其總效率必然更低，此處拟不作贅述。
官方實作與說明
from collections import deque
class Solution:
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root is None:
return []
ret = [] # 結果清單
level_list = deque() # 層周遊節點值隊列
# start with the level 0 with a delimiter
node_queue = deque([root, None]) # 節點隊列
is_order_left = True # 順序填值
while len(node_queue) > 0:
curr_node = node_queue.popleft() # 目前層節點出隊
# 目前層節點周遊
if curr_node:
if is_order_left:
level_list.append(curr_node.val) # 順序添加下一層節點值
else:
level_list.appendleft(curr_node.val) # 逆序添加下一層節點值
# 總是順序添加子下一層節點
if curr_node.left:
node_queue.append(curr_node.left)
if curr_node.right:
node_queue.append(curr_node.right)
# 遇到層分隔符, 處理目前層結果
else:
# we finish one level
ret.append(list(level_list)) # 要先強制類型轉換再添加到結果清單
# add a delimiter to mark the level
if len(node_queue) > 0:
node_queue.append(None) # 添加層分隔符
# prepare for the next level
level_list = deque() # 層周遊節點值隊列
is_order_left = not is_order_left # 添值順序反轉
return ret
2020/08/03 - 55.87% (44ms)
from collections import deque
class Solution:
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root is None:
return []
results = [] # 結果清單
# 尾遞歸 - 記憶體占用小
def dfs(node, level):
if level >= len(results):
results.append(deque([node.val])) # 目前層建立層周遊結果隊列
else:
if level % 2 == 0:
results[level].append(node.val) # 偶數層順序周遊
else:
results[level].appendleft(node.val) # 奇數層逆序周遊
for next_node in [node.left, node.right]: # 遞歸子節點
if next_node is not None:
dfs(next_node, level+1)
# normal level order traversal with DFS
dfs(root, 0)
for i in range(len(results)):
results[i] = list(results[i]) # 強制類型轉換, 否則 results 各元素都是 deque 而非 list
return results
2020/08/03 - 55.87% (44ms)
若官方法一、法二不進行強制類型轉換，令各層節點周遊結果類型由 deque 轉換為 list，會導緻錯誤：
參考文獻
https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/solution/er-cha-shu-de-ju-chi-xing-ceng-ci-bian-li-by-leetc/
107. 二叉樹的層次周遊 II
1. 題目要求
2. 解決過程
個人實作
法一：BFS (疊代-層分隔符)。使用經典的 BFS，最後将結果清單 result 反轉。空間複雜度 O(n)，時間複雜度 O(n)。
2020/08/03 - 98.67% (32ms) - 有這麼快？
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
result = []
Q = collections.deque()
Q.append(root)
Q.append(None) # 層分隔符
## 若不使用層分隔符, 則可用 index 和 len(Q) 替代
while Q[0]: # 不能用 while Q 因為當周遊完畢時 Q 中隻有分隔符 None, 會無限循環
temp = [] # 目前層層序周遊結果
cur = Q.popleft() # 目前層節點出隊
while cur != None:
temp.append(cur.val)
if cur.left:
Q.append(cur.left) # 下一次節點入隊
if cur.right:
Q.append(cur.right) # 下一次節點入隊
cur = Q.popleft() # 目前層節點出隊
Q.append(None) # 層分隔符
result.append(temp)
return result[::-1] # 比這種：[result[i] for i in range(len(result)-1, -1, -1)] 快很多
法一改：BFS (疊代-計數循環)。同法一，隻是層的分割改用計數循環方式。空間複雜度 O(n)，時間複雜度 O(n)。
2020/08/03 - 98.67% (32ms) - 有這麼快？
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
result = [] # 層序周遊結果清單
Q = collections.deque() # 輔助隊列
Q.append(root) # 根節點入隊
## 若不使用 index 和 len(Q), 則可用層分隔符替代
while Q: # 疊代至輔助隊列隊空
nums = len(Q) # 目前層級節點數
result.append([]) # 目前層級空清單初始化
index = 1 # 目前層級節點次序
while index <= nums: # 根據次序依次添加目前層級節點
node = Q.popleft() # 目前層級第 index 個節點, 出隊
result[-1].append(node.val) # 在目前層級空清單 result[-1] 中添加值
if node.left: # 若目前層級節點存在子節點(下一層級), 入隊
Q.append(node.left)
if node.right:
Q.append(node.right)
index += 1 # 目前層級下一個節點次序
return result[::-1]
法二：BFS (尾遞歸)。使用尾遞歸實作 BFS，然後同樣将結果清單 result 反轉。空間複雜度 O(n)，時間複雜度 O(n)。
2020/08/03 - 83.50% (40ms)
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
# 輔助尾遞歸函數
def helper(root, depth, result):
if not root:
return
if depth >= len(result): # 增加目前層周遊結果清單
result.append([])
result[depth].append(root.val) # 添加目前深度的層周遊結果
if root.left:
helper(root.left, depth+1, result)
if root.right:
helper(root.right, depth+1, result)
result = []
helper(root, 0, result)
return result[::-1]
參考文獻
https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
https://blog.csdn.net/qq_39478403/article/details/107329233
111. 二叉樹的最小深度
1. 題目要求
2. 解決過程
測試用例
這道題看似簡單，其實則不然。如果是求二叉樹的 (最大) 深度，則十分容易。然而，此處要求二叉樹的 最小深度，于是存在許多細節問題，邏輯必須理清才能寫對。
[]
[1]
[1,2]
[1,2,3]
[1,2,3,4,null,null,5]
[3,9,20,null,null,15,7]
個人實作
法一：DFS - 線性遞歸。空間複雜度 O(n)，時間複雜度 O(n)。
2020/08/03 - 49.26% (60ms) - 次優
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root: # 空樹
return 0
def helper(root):
if (not root.left) and (not root.right): # 根節點處停止遞歸
return 1
left_depth = helper(root.left) if root.left else float("INf")
right_depth = helper(root.right) if root.right else float("INf")
return 1 + min(left_depth, right_depth)
return helper(root)
法一改：DFS - 尾遞歸。空間複雜度 O(n)，時間複雜度 O(n)。
2020/08/03 - 71.48% (56ms) - 次優
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
def helper(root, depth):
if (not root.left) and (not root.right): # 根節點處停止
return depth
left_depth = helper(root.left, depth+1) if root.left else float("INf")
right_depth = helper(root.right, depth+1) if root.right else float("INf")
return min(left_depth, right_depth)
return helper(root, 1)
法二：BFS - 疊代。使用廣度優先搜尋，一旦發現葉子節點，立即傳回目前深度，即為最小深度。空間複雜度 O(n)，時間複雜度 O(n)。
2020/08/03 - 95.46% (46ms) - 最佳
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
Q = collections.deque()
Q.append(root)
depth = 0 # 目前層(最小)深度
while Q:
nums = len(Q) # 目前層節點數
depth += 1 # 目前層(最小)深度
for _ in range(nums):
cur = Q.popleft()
if not cur.left and not cur.right: # 一旦發現葉子節點, 立即傳回深度
return depth
if cur.left:
Q.append(cur.left)
if cur.right:
Q.append(cur.right)
官方實作與說明 (寫得很差)
class Solution:
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
children = [root.left, root.right]
# if we're at leaf node
if not any(children):
return 1
min_depth = float('inf')
for c in children:
if c:
min_depth = min(self.minDepth(c), min_depth)
return min_depth + 1
class Solution:
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
else:
stack, min_depth = [(1, root),], float('inf')
while stack:
depth, root = stack.pop()
children = [root.left, root.right]
if not any(children):
min_depth = min(depth, min_depth)
for c in children:
if c:
stack.append((depth + 1, c))
return min_depth
from collections import deque
class Solution:
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
else:
node_deque = deque([(1, root),])
while node_deque:
depth, root = node_deque.popleft()
children = [root.left, root.right]
if not any(children):
return depth
for c in children:
if c:
node_deque.append((depth + 1, c))
參考文獻
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode/
112. 路徑總和 II
1. 題目要求
2. 解決過程
個人實作
法一：DFS (preorder) 遞歸實作。通過 DFS 周遊所有可能的路徑 path，每到達一個新節點 root 就記錄到臨時拷貝路徑變量 temp 中 (避免交叉引用混淆結果)，并将和 summ 減去節點值 root.val，以便于到達葉子節點時直接判斷 summ == 0 與否來決定是否将路徑記錄到結果清單 result 中。
2020/08/05 - 91.51% (48ms)
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
if not root:
return []
def dfs(root, summ, path):
"pre-order traversal"
temp = copy.copy(path) # 拷貝路徑, 避免交叉引用混淆結果！
temp.append(root.val) # 記錄路徑
summ -= root.val # 減去節點值
if not root.left and not root.right:
if summ == 0: # 當且僅當葉子節點處和為 0 時符合
result.append(temp) # 記錄符合路徑
return
if root.left:
dfs(root.left, summ, temp)
if root.right:
dfs(root.right, summ, temp)
result = []
dfs(root, sum, [])
return result
其他實作
法一：疊代。
2020/08/05 - 79.63% (52ms)
class Solution:
def pathSum(self, root: TreeNode, sum_: int) -> List[List[int]]:
if not root: return []
stack = [([root.val], root)]
res = []
while stack:
tmp, node = stack.pop()
if not node.right and not node.left and sum(tmp) == sum_:
res.append(tmp)
if node.right:
stack.append((tmp + [node.right.val], node.right))
if node.left:
stack.append((tmp + [node.left.val], node.left))
return res
法二：遞歸。
class Solution:
def pathSum(self, root: TreeNode, sum_: int) -> List[List[int]]:
def helper(root, tmp, sum_):
if not root:
return
if not root.left and not root.right and sum_ - root.val == 0:
tmp += [root.val]
res.append(tmp)
helper(root.left, tmp + [root.val], sum_ - root.val)
helper(root.right, tmp + [root.val], sum_ - root.val)
res = []
helper(root, [], sum_)
return res
參考文獻
https://leetcode-cn.com/problems/path-sum-ii/
https://leetcode-cn.com/problems/path-sum-ii/solution/dfsfei-di-gui-python3-by-baiyizhe/
129. 求根到葉子節點數字之和
1. 題目要求
2. 解決過程
個人實作
法一：DFS (preorder) 遞歸實作。為保證順序和直覺性，使用字元串變量 num 作為中間表示，将深度優先周遊過程中各路徑的數字 root.val 記錄于數字字元串 num 中，一旦到達葉子節點則加入結果清單 result。最後，對所有結果使用 int() 強制轉換類型并求和。空間複雜度 O(n)，時間複雜度 O(n)。
2020/08/06 - 94.00% (36ms)
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
if not root: # 空樹
return 0
def dfs(root, num):
num += str(root.val) # 數字字元串拼接(srt不可變類型, 無深淺拷貝概念)
if not root.left and not root.right: # 葉子節點
result.append(num)
return
if root.left:
dfs(root.left, num)
if root.right:
dfs(root.right, num)
result = [] # 結果清單
dfs(root, "") # 将各路徑數字字元串記錄到結果清單中
return sum(int(i) for i in result)
法一：BFS 疊代實作。原理同上，在周遊到葉子節點的同時，記錄周遊路徑字元串，最後求和。但注意一個優化細節：使用 result.append(int(cur_path)) 最後直接求和，會比目前方案慢許多。空間複雜度 O(n)，時間複雜度 O(n)。
2020/08/07 - 81.94% (40ms)
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
if not root: # 空樹
return 0
result = [] # 結果清單
Q = collections.deque()
Q.append((root, ''))
while Q:
length = len(Q)
for _ in range(length):
cur_node, cur_path = Q.popleft() # 目前節點, 目前路徑
cur_path += str(cur_node.val) # 目前周遊路徑字元串
if not cur_node.left and not cur_node.right:
result.append(cur_path) # 葉子節點處添加路徑字元串到結果清單
continue
if cur_node.left:
Q.append((cur_node.left, cur_path))
if cur_node.right:
Q.append((cur_node.right, cur_path))
return sum(int(i) for i in result)
其他實作
2020/08/08 - 94.02% (36ms) - 最佳
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
def helper(root, i):
if not root:
return 0
temp = i * 10 + root.val
if not root.left and not root.right:
return temp
return helper(root.left, temp) + helper(root.right, temp)
return helper(root, 0)
參考文獻
https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/
199. 二叉樹的右視圖
1. 題目要求
2. 解決過程
個人實作
法一：BFS 疊代實作。隻需要每層在結果清單 result 中添加最後一個節點值 cur.val 即可。空間複雜度 O(n)，時間複雜度 O(n)
2020/08/08 - 81.07% (40ms)
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
if not root:
return []
result = [] # 結果清單
Q = collections.deque() # 輔助隊列
Q.append(root)
while Q:
nums = len(Q) # 目前層節點個數
for i in range(nums):
cur = Q.popleft() # 目前節點
if cur.left:
Q.append(cur.left)
if cur.right:
Q.append(cur.right)
if i == nums - 1:
result.append(cur.val) # 目前層最後一個節點
return result
官方實作與說明
## 有想到用 stack 代替 queue, 但沒想到效果好這麼多
class Solution(object):
def rightSideView(self, root):
rightmost_value_at_depth = dict() # 深度為索引, 存放節點值
max_depth = -1
stack = [(root, 0)] # 輔助棧, 注意不是輔助隊列
while stack:
node, depth = stack.pop() # 總是先彈出最靠右的節點及其深度
if node:
# 維護二叉樹的最大深度
max_depth = max(max_depth, depth)
# 若不存在對應深度的節點才插入
# dict.setdefault(key, default=None)
# 類似get(), 但若 key not in dict, 将添加 key:default 項
rightmost_value_at_depth.setdefault(depth, node.val)
stack.append((node.left, depth+1))
stack.append((node.right, depth+1))
return [rightmost_value_at_depth[depth] for depth in range(max_depth+1)]
2020/08/08 - 98.65% (32ms) - 最佳
# 不如個人實作法一, 此方法記錄了備援的深度資訊
from collections import deque
class Solution(object):
def rightSideView(self, root):
rightmost_value_at_depth = dict() # 深度為索引，存放節點的值
max_depth = -1
queue = deque([(root, 0)]) # 輔助隊列
while queue:
node, depth = queue.popleft()
if node is not None:
# 維護二叉樹的最大深度
max_depth = max(max_depth, depth)
# 由于每一層最後一個通路到的節點才是我們要的答案，是以不斷更新對應深度的資訊即可
rightmost_value_at_depth[depth] = node.val
queue.append((node.left, depth+1))
queue.append((node.right, depth+1))
return [rightmost_value_at_depth[depth] for depth in range(max_depth+1)]
2020/08/08 - 32.05% (48ms)
其他實作
法一：DFS 遞歸實作。
class Solution(object):
def rightSideView(self, root):
def dfs(root, depth):
if not root:
return
if depth == len(res): # 重點
res.append(root.val)
dfs(root.right, depth+1) # 先右
dfs(root.left, depth+1) # 再左
res = []
dfs(root, 0) # 從根節點開始通路，根節點深度是0
return res
2020/08/08 - 81.07% (40ms)
參考文獻
https://leetcode-cn.com/problems/binary-tree-right-side-view/
https://leetcode-cn.com/problems/binary-tree-right-side-view/solution/er-cha-shu-de-you-shi-tu-by-leetcode-solution/
222. 完全二叉樹的節點個數
1. 題目要求
2. 解決過程
個人實作 - 周遊樹線性計數 (未用到完全二叉樹性質)
法一：DFS 遞歸實作。到葉子節點結束計數。空間複雜度 O(1)，時間複雜度 O(n)。
2020/08/08 - 56.64% (104ms)
class Solution:
def countNodes(self, root: TreeNode) -> int:
if not root:
return 0
def dfs(root):
nonlocal num
num += 1 # 目前節點計數
if not root.left and not root.right: # 葉子節點
return
if root.left:
dfs(root.left)
if root.right:
dfs(root.right)
num = 0
dfs(root)
return num
法一改：DFS 遞歸實作。到空節點結束計數。空間複雜度 O(1)，時間複雜度 O(n)。
2020/08/08 - 77.56% (96ms)
class Solution:
def countNodes(self, root: TreeNode) -> int:
def dfs(root):
if not root:
return
nonlocal num
num += 1
dfs(root.left)
dfs(root.right)
num = 0
dfs(root)
return num
法二：BFS 疊代實作。空間複雜度 O(n)，時間複雜度 O(n)。
2020/08/08 - 56.64% (104ms)
class Solution:
def countNodes(self, root: TreeNode) -> int:
if not root:
return 0
num = 0 # 節點數
Q = collections.deque()
Q.append(root)
while Q:
length = len(Q)
num += length # 記錄本層節點數
for _ in range(length):
cur = Q.popleft()
if cur.left:
Q.append(cur.left)
if cur.right:
Q.append(cur.right)
return num
官方實作與說明
class Solution:
def countNodes(self, root: TreeNode) -> int:
return 1 + self.countNodes(root.right) + self.countNodes(root.left) if root else 0
2020/08/08 - 45.29% (108ms)
class Solution:
def compute_depth(self, node: TreeNode) -> int:
"""
Return tree depth in O(d) time.
"""
d = 0 # 深度 depth
while node.left:
node = node.left # 指向下一個左子節點
d += 1 # 深度 +1
return d
def exists(self, idx: int, d: int, node: TreeNode) -> bool:
"""
Last level nodes are enumerated from 0 to 2**d - 1 (left -> right).
Return True if last level node idx exists.
Binary search with O(d) complexity.
"""
left, right = 0, 2**d - 1 # 左、右指針索引
for _ in range(d):
pivot = left + (right - left) // 2 # 中指針索引
# 二分下沉
if idx <= pivot:
node = node.left
right = pivot
else:
node = node.right
left = pivot + 1
return node is not None # 移動到指定節點判斷是否存在
def countNodes(self, root: TreeNode) -> int:
# if the tree is empty
if not root:
return 0
d = self.compute_depth(root) # 樹深度 depth
# if the tree contains 1 node
if d == 0:
return 1
# Last level nodes are enumerated from 0 to 2**d - 1 (left -> right).
# Perform binary search to check how many nodes exist.
left, right = 1, 2**d - 1 # 左、右指針索引
while left <= right:
pivot = left + (right - left) // 2 # 中指針索引
if self.exists(pivot, d, root): # 檢查最後一層中間節點是否存在
left = pivot + 1 # 若存在, 可能還有更多
else:
right = pivot - 1 # 若不存在, 可能還更少
# The tree contains 2**d - 1 nodes on the first (d - 1) levels
# and left nodes on the last level.
return (2**d - 1) + left
2020/08/08 - 97.18% (84ms) - 最佳
參考文獻
https://leetcode-cn.com/problems/count-complete-tree-nodes/
https://leetcode-cn.com/problems/count-complete-tree-nodes/solution/wan-quan-er-cha-shu-de-jie-dian-ge-shu-by-leetcode/
257. 二叉樹的所有路徑
1. 題目要求
2. 解決過程
個人實作
法一：DFS 遞歸實作。空間複雜度 O(n)，時間複雜度 O(n)。
2020/08/08 - 93.26% (36ms)
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
if not root:
return []
def dfs(root, path):
path += str(root.val) # 将節點值加入路徑
if not root.left and not root.right:
result.append(path)
if root.left:
dfs(root.left, path + "->") # 别忘了箭頭
if root.right:
dfs(root.right, path + "->") # 别忘了箭頭
result = []
dfs(root, "")
return result
法二：BFS 疊代實作。空間複雜度 O(n)，時間複雜度 O(n)。
2020/08/08 - 93.26% (36ms)
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
if not root:
return []
result = [] # 結果清單
Q = collections.deque()
Q.append((root, ""))
while Q:
nums = len(Q)
for _ in range(nums):
cur_node, cur_path = Q.popleft()
cur_path += str(cur_node.val) # 目前節點添加到路徑字元串
if not cur_node.left and not cur_node.right:
result.append(cur_path) # 到葉子節點結束并添加路徑
if cur_node.left:
Q.append((cur_node.left, cur_path + "->"))
if cur_node.right:
Q.append((cur_node.right, cur_path + "->"))
return result
官方實作與說明 - 同上
class Solution:
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
def construct_paths(root, path):
if root:
path += str(root.val)
if not root.left and not root.right: # 目前節點是葉子節點
paths.append(path) # 把路徑加入到答案中
else:
path += '->' # 目前節點不是葉子節點，繼續遞歸周遊
construct_paths(root.left, path)
construct_paths(root.right, path)
paths = []
construct_paths(root, '')
return paths
class Solution:
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
if not root:
return []
paths = []
stack = [(root, str(root.val))]
while stack:
node, path = stack.pop()
if not node.left and not node.right:
paths.append(path)
if node.left:
stack.append((node.left, path + '->' + str(node.left.val)))
if node.right:
stack.append((node.right, path + '->' + str(node.right.val)))
return paths
參考文獻
https://leetcode-cn.com/problems/binary-tree-paths/
https://leetcode-cn.com/problems/binary-tree-paths/solution/er-cha-shu-de-suo-you-lu-jing-by-leetcode/
404. 左葉子之和
1. 題目要求
2. 解決過程
個人實作
法一：DFS 遞歸實作。對于左子節點将使用 left_flag = 1 來标記，非左子節點則标記為 0。空間複雜度 O(n)，時間複雜度 O(n)。
2020/08/09 - 40.98% (48ms)
class Solution:
def sumOfLeftLeaves(self, root: TreeNode) -> int:
if not root:
return 0
def dfs(root, left_flag):
if not root.left and not root.right:
return root.val if left_flag else 0
temp_sum = 0
if root.left:
temp_sum += dfs(root.left, 1)
if root.right:
temp_sum += dfs(root.right, 0)
return temp_sum
return dfs(root, 0)
法一改：DFS 遞歸實作。簡化一下。空間複雜度 O(n)，時間複雜度 O(n)。
2020/08/09 - 98.73% (32ms) - 最佳
class Solution:
def sumOfLeftLeaves(self, root: TreeNode) -> int:
def dfs(root, left_flag):
if not root: # 空節點
return 0
if not root.left and not root.right: # 葉子節點
return root.val if left_flag else 0
return dfs(root.left, 1) + dfs(root.right, 0) # 求和
return dfs(root, 0)
法二：BFS 疊代實作。原理同法一。左子節點用 left_flag = 1 來标記，非左子節點則标記為 0。空間複雜度 O(n)，時間複雜度 O(n)。
2020/08/09 - 40.98% (48ms)
class Solution:
def sumOfLeftLeaves(self, root: TreeNode) -> int:
if not root:
return 0
left_sum = 0
Q = collections.deque()
Q.append((root, 0))
while Q:
nums = len(Q)
for _ in range(nums):
cur_node, left_flag = Q.popleft()
if not cur_node.left and not cur_node.right:
if left_flag:
left_sum += cur_node.val
continue
if cur_node.left:
Q.append((cur_node.left, 1))
if cur_node.right:
Q.append((cur_node.right, 0))
return left_sum
參考文獻
https://leetcode-cn.com/problems/sum-of-left-leaves/