本文主要是介绍Leetcode 112-路径总和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
题解
方法一
- 判断树中是否有某路径，可以判断左子树或右子树中是否有该路径，即采用left== true || right==true判断，否则返回值需为false
- 递归+回溯
//记录路径值，将所有路径值加入map
class Solution {HashMap<Integer,Integer> map = new HashMap<>();public boolean hasPathSum(TreeNode root, int targetSum) {//pathSum(root,targetSum,0);//if(map.containsKey(targetSum)) return true;return pathSum(root,targetSum,0);}public boolean pathSum(TreeNode root, int targetSum,int sum){//if(root==null) return false;//当前层需做的步骤sum+=root.val;//为叶节点if(root.left==null&&root.right==null){if(sum==targetSum){// map.put(sum,1);return true;}else{return false;}}//当前节点的左右子树在要有一个为空，则返回true，否则返回falseif(pathSum(root.left,targetSum,sum)||pathSum(root.right,targetSum,sum)) return true;return false;}
}
方法二
记录路径值，将所有路径值加入map
如果拿list或者map作为全局变量记录路径值，则可以不需要返回值
class Solution {HashMap<Integer,Integer> map = new HashMap<>();public boolean hasPathSum(TreeNode root, int targetSum) {pathSum(root,targetSum,0);if(map.containsKey(targetSum)) return true;return false;}public void pathSum(TreeNode root, int targetSum,int sum){//边界条件if(root==null) return;sum+=root.val;//为叶节点if(root.left==null&&root.right==null){if(sum==targetSum){map.put(sum,1);}}//int类型不需要回溯，即插销当前操作pathSum(root.left,targetSum,sum);pathSum(root.right,targetSum,sum);return;}}
这篇关于Leetcode 112-路径总和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
