东莞品牌网站设计,哪家代理注册公司好,大兴专业网站建设价钱,郑州做网站熊掌号1.0112. 路径总和
1.1 题目大意 描述#xff1a;给定一个二叉树的根节点 root 和一个值 targetSum。
要求#xff1a;判断该树中是否存在从根节点到叶子节点的路径#xff0c;使得这条路径上所有节点值相加等于 targetSum。如果存在#xff0c;返回 True#xff1b;否则…1.0112. 路径总和
1.1 题目大意 描述给定一个二叉树的根节点 root 和一个值 targetSum。
要求判断该树中是否存在从根节点到叶子节点的路径使得这条路径上所有节点值相加等于 targetSum。如果存在返回 True否则返回 False。 说明 树中节点的数目在范围[0,5000]
输入root [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum 22
输出true
解释等于目标和的根节点到叶节点路径如上图所示。解题思路
按照题意是从根节点的值累加叶节点的值是否等于每个值首先判断根节点是否存在然后开始依次往下找到最底层的节点即既没有左节点也没有右节点的节点依次累加满足累加值等于指定值累加到的那个节点既没有左节点也没有右节点。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def hasPathSum(self, root: Optional[TreeNode], target: int) - bool:if not root:return Falsereturn self.dfs(root,target,[root.val])def dfs(self,root,target,path):if not root:return Falseif sum(path)target and not root.left and not root.right:return Trueleft_flag,right_flagFalse,Falseif root.left:left_flagself.dfs(root.left,target,path[root.left.val])if root.right:right_flagself.dfs(root.right,target,path[root.right.val])return left_flag or right_flag2.0113. 路径总和 II
2.1 题目大意 描述给定一棵二叉树的根节点 root 和一个整数目标 targetSum。
要求找出「所有从根节点到叶子节点路径总和」等于给定目标和 targetSum 的路径。
说明
叶子节点指没有子节点的节点。 树中节点的数目在范围[0,5000]
输入root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum 22
输出[[5,4,11,2],[5,8,4,5]]# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) - List[List[int]]:res,path[],[]def recur(root,tar):if not root:returnpath.append(root.val)tar-root.valif tar0 and not root.left and not root.right:res.append(list(path))recur(root.left,tar)recur(root.right,tar)path.pop()recur(root,targetSum)return res3.0101. 对称二叉树
3.1 题目大意 描述给定一个二叉树的根节点 root。
要求判断该二叉树是否是左右对称的。 说明 树中节点数目在范围[1,1000]内。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def isSymmetric(self, root: Optional[TreeNode]) - bool:def recur(left,right):if not left and not right:return Trueif not right or not left or left.val!right.val:return Falsereturn recur(left.left,right.right) and recur(left.right,right.left)return recur(root.left,root.right) 1.0124. 二叉树中的最大路径和
1.1 题目大意 描述给定一个二叉树的根节点 root。 要求返回其最大路径和。 说明 路径从树中的任意节点出发沿父节点——子节点连接到达任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点且不一定经过根节点。 路径和路径中各节点值的总和。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def maxPathSum(self, root: Optional[TreeNode]) - int:ans-infdef dfs(root):if not root:return 0l_valdfs(root.left)r_valdfs(root.right)nonlocal ansansmax(ans,l_valr_valroot.val)return max(max(l_val,r_val)root.val,0)dfs(root)return ans
