首页 > 代码库 > [leetcode]Path Sum II

[leetcode]Path Sum II

2024-07-15 03:51:35   218人阅读

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path‘s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5             /             4   8           /   /           11  13  4         /  \    /         7    2  5   1

return

[   [5,4,11,2],   [5,8,4,5]]

 

 

算法思路：

跟[leetcode]Path Sum区别不大，dfs

代码如下：

 1 public class Solution { 2     List<List<Integer>> res = new ArrayList<List<Integer>>(); 3     public List<List<Integer>> pathSum(TreeNode root, int sum) { 4         if(root == null) return res; 5         List<Integer> list = new ArrayList<Integer>(); 6         dfs(list, root, sum); 7         return res; 8     } 9     public void dfs(List<Integer> list,TreeNode root,int sum){10         if(root.left == null && root.right == null && root.val == sum){11             list.add(sum);12             res.add(new ArrayList<Integer>(list));13             list.remove(list.size() - 1);14             return;15         }16         if(root.left != null){17             list.add(root.val);18             dfs(list, root.left, sum - root.val);19             list.remove(list.size() - 1);20         }21         if(root.right!= null){22             list.add(root.val);23             dfs(list, root.right, sum - root.val);24             list.remove(list.size() - 1);25         }26     }27 }

 


联系
我们