第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,
LinkedHashMap基本用法&使用实现简单缓存 dedecms网站被黑 劫持到其他网站如何解决苹果不送充填器耳机真为环保?可能还是为了赚钱吧图片格式转换错误总结-myBatis plus 分页numpy:多维数组的创建用C语言做很简单的飞机游戏Keras保存与加载模型(JSON+HDF5)福布斯中国汽车富豪榜:何小鹏第11 李想第14 李斌第15hive大量小文件处理方法总结