力扣-路径总和问题

路径总和 --简单

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

直接果断dfs做题就行了。

这里是C的代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
bool hasPathSum(struct TreeNode* root, int targetSum){if(root==NULL)return false;elseif(targetSum==root->val&&root->right==NULL&&root->left==NULL)return true;elsereturn (hasPathSum((root->right),targetSum-root->val))+(hasPathSum((root->left),targetSum-root->val));}

这里是Java的代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if(root == null)return false;else if(root.left == null && root.right == null && targetSum == root.val)return true;else return (hasPathSum((root.right),targetSum-root.val)) ||(hasPathSum((root.left),targetSum-root.val));}
}

路径总和2 --中等

113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {LinkedList<List<Integer>> res = new LinkedList<>();//最后返回的结果集合LinkedList<Integer> path = new LinkedList<>();    //路径集合void dfs(TreeNode root,int targetSum){if(root == null) {return;}path.add(root.val);dfs(root.left,targetSum-root.val);dfs(root.right,targetSum-root.val);     if(targetSum == root.val && root.left == null && root.right == null)res.add(new LinkedList(path));    //感觉最重要的就是这里了，new LinkedList(path)直接把path的值赋给新的对象了。path.removeLast();    }public List<List<Integer>> pathSum(TreeNode root, int targetSum) {if(root == null)return res;dfs(root,targetSum);return res;}
}

路径总和3

437. 路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

这个题目就是求每个节点的到另一个节点路径总和会等于targetsum吗？

所以直接得出：直接对每个结点进行dfs就可以解决了。

这个题目还有一种做法，就是用bfs＋dfs来做，bfs遍历树，然后dfs求每个结点的路径总和。

这个题目有个注意点，就是测试数据中，有个很大的结点值，必须要用long来接收，int会越界出错，属实让我触不及防了。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int pathSum(TreeNode root, int targetSum) { if(root==null){ return 0; }int res = 0;long ts = (long) targetSum;res += PointCount(root, ts);res += pathSum(root.left, (int)ts);res += pathSum(root.right, (int)ts);return res;}public int PointCount(TreeNode root, long targetSum){int res = 0;if(root == null){return 0;}long val = (long) root.val;if(val == targetSum){res++;}res += PointCount(root.left, targetSum-val);res += PointCount(root.right, targetSum-val);return res;
}
}