相關(guān)推薦
python coding with ChatGPT 打卡第12天| 二叉樹(shù)：理論基礎(chǔ)
python coding with ChatGPT 打卡第13天| 二叉樹(shù)的深度優(yōu)先遍歷
python coding with ChatGPT 打卡第14天| 二叉樹(shù)的廣度優(yōu)先遍歷
python coding with ChatGPT 打卡第15天| 二叉樹(shù)：翻轉(zhuǎn)二叉樹(shù)、對(duì)稱二叉樹(shù)
python coding with ChatGPT 打卡第16天| 二叉樹(shù)：完全二叉樹(shù)、平衡二叉樹(shù)、二叉樹(shù)的所有路徑、左葉子之和

找樹(shù)左下角的值

Key Points

找出樹(shù)的最后一行的最左邊的值

相關(guān)題目

513. 找樹(shù)左下角的值

視頻講解

遞歸中帶著回溯

重點(diǎn)分析

方法一：層序遍歷

def findBottomLeftValue(root):queue_record = [root]res = root.valwhile queue_record:level_size = len(queue_record)for i in range(level_size):node = queue_record.pop(0)if i==0:res = node.valif node.left:queue_record.append(node.left)if node.right:queue_record.append(node.right)return res

方法二：層序遍歷簡(jiǎn)潔版

class Solution(object):def findBottomLeftValue(self, root):if not root:return Nonequeue = [root]while queue:current = queue.pop(0)# 先右后左加入隊(duì)列，確保左邊的節(jié)點(diǎn)最后被處理，從而保留在current中if current.right:queue.append(current.right)if current.left:queue.append(current.left)# 循環(huán)結(jié)束時(shí)，current中存儲(chǔ)的是最后一層最左邊的節(jié)點(diǎn)return current.val

這段代碼使用了BFS來(lái)確保按層遍歷樹(shù)的節(jié)點(diǎn)，并且通過(guò)在每層遍歷時(shí)記錄遍歷到的第一個(gè)節(jié)點(diǎn)值，最終找到了最后一行最左邊的值。請(qǐng)注意，這里故意先將右子節(jié)點(diǎn)加入隊(duì)列，然后加入左子節(jié)點(diǎn)，是為了在處理每一層的節(jié)點(diǎn)時(shí)，最后處理左子節(jié)點(diǎn)，但是對(duì)于尋找最后一行最左邊的值的目的而言，只需要記錄每一層第一次訪問(wèn)的節(jié)點(diǎn)即可，因此實(shí)際上你可以按照正常的順序（先左后右）加入隊(duì)列，然后最后處理的節(jié)點(diǎn)即為所求。這樣的處理方式更直觀且易于理解。

方法三：遞歸法

class Solution:def findBottomLeftValue(self, root: TreeNode) -> int:self.max_depth = float('-inf')self.result = Noneself.traversal(root, 0)return self.resultdef traversal(self, node, depth):if not node.left and not node.right:if depth > self.max_depth:self.max_depth = depthself.result = node.valreturnif node.left:self.traversal(node.left, depth+1)if node.right:self.traversal(node.right, depth+1)

遞歸的另一種寫(xiě)法，由ChatGPT提供

路徑總和

Key Points

葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

相關(guān)題目

112. 路徑總和
113. 路徑總和ii

視頻講解

路徑總和

重點(diǎn)分析

112
方法一：遞歸

def hasPathSum(root: TreeNode, targetSum: int) -> bool:if not root:return False# 更新目標(biāo)和targetSum -= root.val# 如果是葉子節(jié)點(diǎn)，檢查目標(biāo)和是否為0if not root.left and not root.right:return targetSum == 0# 遞歸遍歷左右子節(jié)點(diǎn)return hasPathSum(root.left, targetSum) or hasPathSum(root.right, targetSum)

方法二：迭代法

def hasPathSum(root, targetSum):if not root:return Falsestack_record = [(root, root.val)]while stack_record:node, value = stack_record.pop()if not node.left and not node.right:if value == targetSum:return Trueelse:if node.right:stack_record.append((node.right, value+node.right.val))if node.left:stack_record.append((node.left, value + node.left.val))return False

113 方法一：遞歸法

class Solution:def pathSum(self, root: TreeNode, targetSum: int) -> [[int]]:result = []self.dfs(root, targetSum, [], result)return resultdef dfs(self, node, targetSum, path, result):if not node:return# 添加當(dāng)前節(jié)點(diǎn)到路徑path.append(node.val)# 檢查是否是葉子節(jié)點(diǎn)且路徑總和等于目標(biāo)和if not node.left and not node.right and sum(path) == targetSum:result.append(list(path))else:# 遞歸遍歷左右子節(jié)點(diǎn)self.dfs(node.left, targetSum, path, result)self.dfs(node.right, targetSum, path, result)# 回溯前去除當(dāng)前節(jié)點(diǎn)path.pop()# 示例使用
# 假設(shè)有一個(gè)二叉樹(shù)和目標(biāo)和，可以創(chuàng)建TreeNode實(shí)例并調(diào)用Solution().pathSum(root, targetSum)來(lái)獲取結(jié)果

方法二：迭代法

def pathSum(root, targetSum):if not root:return []stack_record = [(root, [root.val])]res = []while stack_record:node, value_list = stack_record.pop()if not node.left and not node.right:if sum(value_list) == targetSum:res.append(value_list)else:if node.right:stack_record.append((node.right, value_list+[node.right.val]))if node.left:stack_record.append((node.left, value_list + [node.left.val]))return res