Title: Path Sum II Source: leetcode.com
Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.
sum = 22
|
1 2 3 4 5 6 7 |
5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 |
return
|
1 2 3 4 |
[ [5,4,11,2], [5,8,4,5] ] |
Python solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
''' https://leetcode.com/problems/path-sum-ii/ ''' # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def __init__(self): self.sum = 0 self.paths = [] def helper(self, root, cur_sum, path): cur_sum += root.val path = path + [root.val] if not (root.left or root.right): if cur_sum == self.sum: self.paths.append(path) return if root.left: self.helper(root.left, cur_sum, path) if root.right: self.helper(root.right, cur_sum, path) def pathSum(self, root, sum): """ :type root: TreeNode :type sum: int :rtype: List[List[int]] """ if not root: return self.paths self.sum = sum self.helper(root, 0, []) return self.paths |
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
/* https://leetcode.com/problems/path-sum-ii/ */ import java.util.List; import java.util.ArrayList; class PathSumII { // use dfs to traverse tree recursively and if the sum of the path from root // to leaf is equals to given sum add that path to list // use backtracking public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> pathList = new ArrayList<>(); if(root==null) return pathList; List<Integer> path = new ArrayList<>(); pathSumHelper(root, sum, 0, path, pathList); return pathList; } public void pathSumHelper(TreeNode root, int sum, int currentSum, List<Integer> path, List<List<Integer>> pathList) { if(root!=null) { path.add(root.value); //System.out.println(path); currentSum = currentSum + root.value; if(root.left == null && root.right == null) { if(currentSum == sum) { pathList.add(new ArrayList<Integer>(path)); } } else { if(root.left!=null) pathSumHelper(root.left, sum, currentSum, path, pathList); if(root.right!=null) pathSumHelper(root.right, sum, currentSum, path, pathList); } int temp = path.remove(path.size()-1); currentSum = currentSum - temp; } } public static void main(String args[]) { TreeNode root = new TreeNode(5); root.left = new TreeNode(4); root.left.left = new TreeNode(11); root.left.left.left = new TreeNode(7); root.left.left.right = new TreeNode(2); root.right = new TreeNode(8); root.right.left = new TreeNode(13); root.right.right = new TreeNode(4); root.right.right.left = new TreeNode(5); root.right.right.right = new TreeNode(1); PathSumII p = new PathSumII(); System.out.println(p.pathSum(root, 22)); } } |