Contents
Question
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. Note: A leaf is a node with no children. 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
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { List<List<Integer>> rlist = new ArrayList<>(); public List<List<Integer>> pathSum(TreeNode root, int sum) { treePath(root,new ArrayList(),sum); return rlist; } private void treePath(TreeNode root,List list,int sum){ if(root == null) return; if(root.left == null && root.right == null){ if(sum - root.val == 0){ List<Integer> copy = new LinkedList<>(list); copy.add(root.val); rlist.add(copy); } return; } list.add(root.val); treePath(root.left,list,sum - root.val); treePath(root.right,list,sum - root.val); list.remove(list.size()-1); } }