力扣-路径总和问题

 路径总和 --简单

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;
    else
        if(targetSum==root->val&&root->right==NULL&&root->left==NULL)
        return true;
        else
        return (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> res = new LinkedList<>();//最后返回的结果集合
    LinkedList 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> 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;
}
}

总结

其实这种路径问题就是围绕dfs和bfs来做题的。掌握好dfs和bfs就可以基本拿捏这种类型的题目了。