leetcode 112. Path Sum, 113. Path Sum II | 112,113. 路径总和 I, II（Java）

超、凢脫俗 2022-09-03 01:22 184阅读 0赞

## 题目 ##

[https://leetcode.com/problems/path-sum/][https_leetcode.com_problems_path-sum]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

[https://leetcode.com/problems/path-sum-ii/][https_leetcode.com_problems_path-sum-ii]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

## 题解 ##

简单的遍历二叉树，不解释，直接上代码

##### 112. Path Sum #####

/** * 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) { 
            return dfs(root, 0, targetSum);
        }
    
        public boolean dfs(TreeNode node, int sum, int target) { 
            if (node == null) return false;
            if (node.left == null && node.right == null) return sum + node.val == target;
    
            return dfs(node.left, sum + node.val, target) || dfs(node.right, sum + node.val, target);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

##### 113. Path Sum II #####

/** * 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 { 
        List<List<Integer>> res;
    
        public List<List<Integer>> pathSum(TreeNode root, int targetSum) { 
            res = new ArrayList<>();
            dfs(root, 0, targetSum,new ArrayList<>());
            return res;
        }
    
        public void dfs(TreeNode node, int sum, int target, List<Integer> list) { 
            if (node == null) return;
    
            List<Integer> newList = new ArrayList<>(list);
            newList.add(node.val);
            if (node.left == null && node.right == null && sum + node.val == target) {  // 是叶子
                res.add(newList);
            }
    
            dfs(node.left, sum + node.val, target, newList);
            dfs(node.right, sum + node.val, target, newList);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]

[https_leetcode.com_problems_path-sum]: https://leetcode.com/problems/path-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/af83df3a556e491695b8f90febc9e886.png
[https_leetcode.com_problems_path-sum-ii]: https://leetcode.com/problems/path-sum-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/9d3cddf508304c8aaf73e7b5088ce121.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/93816d6a4bdd4ee1b3842becaaa078bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]: /images/20220829/0b1c62e8aa7e47e8ac2e411123ba9f89.png