第13天
2020.07.07 周二
今天是高三同学们高考的日子,我一个准大三紧张个锤锤。
难度系数:简单
题目:112路径总和
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树,以及目标和 sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 返回 true,
因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
——————————我是分割线——————————
解法:
思路:深搜
所谓DFS深度优先搜索法,不过就是不撞南墙不回头。一直往下走,走不通就回头换条路再走。
深搜的实质是穷举,按照一定的顺序和规则去尝试,直到找到问题的解。

代码:
(这里放的代码是我编译器测试的代码)
# leetcode112路径总和 2020.07.07 # Definition for a binary tree node. class
TreeNode(object): def __init__(self, x,left=0,right=0): self.val = x self.left =
left self.right = right class Solution(object): def hasPathSum(self, root, sum)
: """ :type root: TreeNode :type sum: int :rtype: bool """ if not root:
#节点为空则返回False return False if not root.left and not root.right: #左右子树为空 即为叶子节点
return sum==root.val #判断sum是否等于当前节点的值 return self.hasPathSum(root.left,sum-root.
val) or self.hasPathSum(root.right,sum-root.val) tree1=TreeNode(7) tree2=
TreeNode(2) tree3=TreeNode(1) tree4=TreeNode(4,0,tree3) tree5=TreeNode(13) tree6
=TreeNode(11,tree1,tree2) tree7=TreeNode(4,tree6) tree8=TreeNode(8,tree5,tree4)
root=TreeNode(5,tree7,tree8) sum = 22 print(Solution().hasPathSum(root,sum))
#结果 True

技术
©2019-2020 Toolsou All rights reserved,
Java开发2020年最新常见面试题整理【Spring源码分析】42-@Conditional详解element-ui踩坑记录神仙面试宝典你有了吗?半月看完25大专题,居然斩获阿里P8offer使用css样式设计一个简单的html登陆界面XCTF攻防世界web新手练习_ 9_command_executionJS中的解构赋值的详解与具体用途Python Web 框架elementui 穿梭框 el-transfer 展示列表内容文字过长ConcurrentHashMap实现原理及源码解析