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] ]
Solution: Backtracking is the most space-efficient way to solve this.
Code in Java: Non-backtracking.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { private ArrayList<List<Integer>> result; void pathSum( TreeNode root, int sum, ArrayList<Integer> path ) { if (root == null) { return; } path.add(root.val); sum -= root.val; if (root.left == null && root.right == null && sum == 0) { result.add(new ArrayList<Integer>(path)); } pathSum(root.left, sum, new ArrayList(path)); pathSum(root.right, sum, new ArrayList(path)); } public List<List<Integer>> pathSum(TreeNode root, int sum) { result = new ArrayList<List<Integer>>(); pathSum(root, sum, new ArrayList<Integer>()); return result; } }
Code in Java: Backtracking.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { private ArrayList<List<Integer>> result; ArrayList<Integer> path; void pathSumBackTracking( TreeNode root, int sum ) { if (root == null) { return; } path.add(root.val); sum -= root.val; if (root.left == null && root.right == null && sum == 0) { result.add(new ArrayList<Integer>(path)); } pathSumBackTracking(root.left, sum); pathSumBackTracking(root.right, sum); path.remove(path.size() - 1); } public List<List<Integer>> pathSum(TreeNode root, int sum) { result = new ArrayList<List<Integer>>(); path = new ArrayList<Integer>(); pathSumBackTracking(root, sum); return result; } }
No comments:
Post a Comment