????????這篇可以主要關(guān)注一下如何確定遞歸時(shí)是否需要返回值。

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

給定一個(gè)二叉樹(shù)的根節(jié)點(diǎn)，請(qǐng)找出該二叉樹(shù)的?最底層最左邊?節(jié)點(diǎn)的值。

思路1 層序遍歷

class Solution:def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:if not root: return -1# leverOrderfrom collections import dequeque = deque()que.append(root)while que:size = len(que)for i in range(size):node = que.popleft()if i == 0:ans = node.valif node.left: que.append(node.left)if node.right: que.append(node.right)return ans

思路2 深度優(yōu)先方法要困難一些，遞歸判斷結(jié)點(diǎn)是否是深度最大的葉子結(jié)點(diǎn)，只遍歷，沒(méi)有進(jìn)行什么操作，所以不需要有返回值。這種寫法是隱含了回溯的，不需要自己寫，因?yàn)楹瘮?shù)調(diào)用完形參就釋放了。

class Solution:def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:def isleaf(root):return root and not root.left and not root.right# 深度優(yōu)先 max_depth = 0target = root.valdef dfs(root, depth):nonlocal max_depth, targetif not root: return depth += 1if isleaf(root):if depth > max_depth:max_depth = depthtarget = root.valdfs(root.left, depth)dfs(root.right, depth)dfs(root, 0)return target

下面這種寫法是把回溯寫出來(lái)了，因?yàn)閐epth一直在變的。

class Solution:def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:def isleaf(root):return root and not root.left and not root.rightleftval = root.valmax_d = 0depth = 0def dfs(root):nonlocal leftval, max_d, depthif not root: returndepth += 1if isleaf(root):if depth > max_d:max_d = depthleftval = root.valif root.left:dfs(root.left)depth -= 1if root.right:dfs(root.right)depth -= 1dfs(root)return leftval

LC112. 路徑總和???????

給你二叉樹(shù)的根節(jié)點(diǎn)?root 和一個(gè)表示目標(biāo)和的整數(shù)?targetSum 。判斷該樹(shù)中是否存在 根節(jié)點(diǎn)到葉子節(jié)點(diǎn) 的路徑，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和?targetSum 。如果存在，返回 true ；否則，返回 false。

下面是我自己的寫法，雖然AC了（其中要注意ans寫成nonlocal），但是問(wèn)題是找到了目標(biāo)路徑和之后還是會(huì)進(jìn)行一整個(gè)樹(shù)的遍歷。

class Solution:def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:def isleaf(root):return root and not root.left and not root.right# 先序遍歷ans = Falsepathsum = 0def dfs(root, pathsum):nonlocal ansif not root: return pathsum += root.valif isleaf(root):if pathsum == targetSum:ans = Trueif root.left: dfs(root.left, pathsum)if root.right: dfs(root.right, pathsum)dfs(root,pathsum)return ans

本題搜索出一條符合條件的路徑即可，所以遞歸一定要有返回值，遇到符合的路徑要及時(shí)返回。下面的寫法好多了。

class Solution:def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:def isleaf(root):return root and not root.left and not root.right# 先序遍歷def dfs(root, pathsum) -> bool:pathsum += root.val# 葉子結(jié)點(diǎn)如果找到了路徑和，True；否則Falseif isleaf(root):if pathsum == targetSum:return Trueelse:return False# 如果左孩子里面找到了路徑和，返回Trueif root.left: if dfs(root.left, pathsum):return True# 如果右孩子里面找到了路徑和，返回Trueif root.right: if dfs(root.right, pathsum):return True# 都沒(méi)有找到，返回Falsereturn Falseif not root: return False #這一行也重要return dfs(root,0)

LC113. 路徑總和 II

給你二叉樹(shù)的根節(jié)點(diǎn)?root?和一個(gè)整數(shù)目標(biāo)和?targetSum?，找出所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)路徑總和等于給定目標(biāo)和的路徑。

本題是需要遍歷完整棵樹(shù)，且不用處理遞歸返回值，就不需要返回值。

class Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:def isleaf(root):return root and not root.left and not root.rightpaths = []path = []def dfs(root, sum_pre):if not root: returnpath.append(root.val)sum_pre += root.val# print(sum_pre, path)if isleaf(root) and sum_pre == targetSum: #寫的時(shí)候isleaf后面的(root)也忘了寫，就變成了是否存在isleaf函數(shù)，就一直都是True。多花了時(shí)間調(diào)試，寫的時(shí)候就要慢慢細(xì)致地寫。paths.append(path[:]) #[:]不要忘了加if root.left:dfs(root.left, sum_pre)path.pop()if root.right:dfs(root.right, sum_pre)path.pop()dfs(root, 0)return paths

LC106. 從中序與后序遍歷序列構(gòu)造二叉樹(shù)???????

這題沒(méi)有看答案一次AC了，大晚上的開(kāi)心了好一會(huì)兒～這草稿也是只有自己能看懂了LOL。

本題需要遍歷完整棵樹(shù)，但需要對(duì)遞歸返回值（結(jié)點(diǎn)）進(jìn)行處理（鏈接），所以需要有返回值。

# 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 class Solution:def find(self, nums, val):for i, num in enumerate(nums):if num == val:return ireturn -1def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:# def constructTree(inorder, postorder: List[int]) -> Optional[TreeNode]:if not inorder: return Noneif len(inorder) == 1: return TreeNode(inorder[0])m = postorder[-1]node = TreeNode(m)i = self.find(inorder, m)print(m,i)l_inorder = inorder[0:i]r_inorder = inorder[i+1:]l_postorder = postorder[0:i]r_postorder = postorder[i:-1]node.left = self.buildTree(l_inorder,l_postorder)node.right = self.buildTree(r_inorder,r_postorder)return node

LC105. 從前序與中序遍歷序列構(gòu)造二叉樹(shù)?

給定兩個(gè)整數(shù)數(shù)組?preorder 和 inorder?，其中?preorder 是二叉樹(shù)的先序遍歷， inorder?是同一棵樹(shù)的中序遍歷，請(qǐng)構(gòu)造二叉樹(shù)并返回其根節(jié)點(diǎn)。

和上題一樣的寫法，但寫find函數(shù)時(shí)出現(xiàn)了小問(wèn)題，要在循環(huán)結(jié)束時(shí)還沒(méi)return才返回-1。

class Solution:def find(self, nums, val):for i, num in enumerate(nums):if num == val:return ireturn -1def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:if not preorder: return NoneNode = TreeNode(preorder[0])mid = preorder[0]i = self.find(inorder, mid)l_inorder, r_inorder = inorder[0:i], inorder[i+1:]l_preorder, r_preorder = preorder[1:i+1], preorder[i+1:]Node.left = self.buildTree(l_preorder, l_inorder)Node.right = self.buildTree(r_preorder, r_inorder)return Node

看了答案之后發(fā)現(xiàn)在list中查找元素的時(shí)候，不需要自己寫函數(shù)，用自身的index方法，直接i = inorder.index(mid)即可。

明天加油～?

參考資料：???????路徑總和-代碼隨想錄

總結(jié)

以上是生活随笔為你收集整理的找树左下角的值+路径总和+从前序和中序遍历序列构造二叉树（day18*）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。