浙江平台网站建设找哪家,wordpress flat theme,永久不收费免费的软件,百度云 网站备案文章目录 题目描述解题思路代码 题目描述
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径#xff0c;这条路径上所有节点值相加等于目标和 targetSum 。如果存在#xff0c;返回 true #xff1b;否则#xff0… 文章目录 题目描述解题思路代码 题目描述
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径这条路径上所有节点值相加等于目标和 targetSum 。如果存在返回 true 否则返回 false 。
叶子节点 是指没有子节点的节点。
示例 1
输入root [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum 22 输出true 解释等于目标和的根节点到叶节点路径如上图所示。 示例 2
输入root [1,2,3], targetSum 5 输出false 解释树中存在两条根节点到叶子节点的路径 (1 -- 2): 和为 3 (1 -- 3): 和为 4 不存在 sum 5 的根节点到叶子节点的路径。 示例 3
输入root [], targetSum 0 输出false 解释由于树是空的所以不存在根节点到叶子节点的路径。
提示
树中节点的数目在范围 [0, 5000] 内 -1000 Node.val 1000 -1000 targetSum 1000
解题思路
在代码中详细注释了
代码
class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if (rootnull){return false;}return traversal(root,targetSum-root.val);}public boolean traversal(TreeNode root,int targetSum){//使用递归加上回溯的方法//这个问题中使用前中后遍历的方式都行//递归出口是当前节点是叶子节点并且targetsum已经等于0了表示已经找到了一条路径if (root.leftnullroot.rightnulltargetSum0){return true;}//如果到叶节点了但是路径节点之和并不等于targetSum就返回falseif (root.leftnullroot.rightnulltargetSum!0){return false;}//往左子树递归遍历if (root.left!null){//减去左孩子的valtargetSum targetSum-root.left.val;//如果左孩子下面的路径返回的是true就返回trueif (traversal(root.left,targetSum)){return true;}//没有进入上面的if条件表示没有找到一条满足的路径所以要继续回溯targetSum targetSumroot.left.val;}//往右子树递归遍历if (root.right!null){//减去左孩子的valtargetSum targetSum-root.right.val;//如果左孩子下面的路径返回的是true就返回trueif (traversal(root.right,targetSum)){return true;}//没有进入上面的if条件表示没有找到一条满足的路径所以要继续回溯targetSum targetSumroot.right.val;}return false;}
}
