当前位置：首页 > news >正文

算法训练第十六天

news 2025/6/13 10:05:41

513.找树左下角的值

代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def findBottomLeftValue(self, root):""":type root: Optional[TreeNode]:rtype: int"""ans = []queue = []if not root:return ansqueue.append(root)size = 1while queue:res = []while size>0:t = queue.pop(0)res.append(t.val)if t.left:queue.append(t.left)if t.right:queue.append(t.right)size-=1ans.append(res)size=len(queue)return ans[len(ans)-1][0]

112. 路径总和

代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def hasPathSum(self, root, targetSum):""":type root: Optional[TreeNode]:type targetSum: int:rtype: bool"""if root is None:return Falseans = [False]res = []self.find(root,res,ans,targetSum)return ans[0]def find(self,node,res,ans,targetSum):res.append(node.val)if node.left is None and node.right is None:if sum(res)==targetSum:ans[0]=Trueres.pop()returnif node.left:self.find(node.left,res,ans,targetSum)if node.right:self.find(node.right,res,ans,targetSum)res.pop()return

113. 路径总和Ⅱ

代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def pathSum(self, root, targetSum):import copy""":type root: Optional[TreeNode]:type targetSum: int:rtype: List[List[int]]"""if root is None:return []ans = []res = []self.find(root,res,ans,targetSum)return ansdef find(self,node,res,ans,targetSum):res.append(node.val)if node.left is None and node.right is None:if sum(res)==targetSum:ans.append(copy.deepcopy(res))res.pop()returnif node.left:self.find(node.left,res,ans,targetSum)if node.right:self.find(node.right,res,ans,targetSum)res.pop()return

106.从中序与后序遍历序列构造二叉树

代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def buildTree(self, inorder, postorder):import copy""":type inorder: List[int]:type postorder: List[int]:rtype: Optional[TreeNode]"""if len(postorder)==0:return Noneroot = TreeNode()val = postorder[len(postorder)-1]root.val = valif len(postorder)==1:return rootidx = inorder.index(val)root.left = self.find(inorder,postorder,0,idx-1,0,0+idx-1-0)root.right = self.find(inorder,postorder,idx+1,len(inorder)-1,idx,len(postorder)-2)return rootdef find(self,inorder,postorder,il,lr,pl,pr):if pr-pl+1<=0:return Nonenode = TreeNode()node.val = postorder[pr]if pr-pl+1==1:return nodeidx = inorder.index(node.val)node.left = self.find(inorder,postorder,il,idx-1,pl,pl+idx-1-il)node.right = self.find(inorder,postorder,idx+1,lr,pl+idx-1-il+1,pr-1)return node