Leaf Path Sum
出处
Get all the paths (always starts from the root and ends at leaf) in a binary tree, whose sum would be equal to given value.
Solution
本题的处理办法基本与 path-sum.md 完全一致,唯一的区别在于现在要求一定是root-to-leaf paths,故当path和为给定值的时候还需要判断当前节点是否是叶节点。
Complexity
时间、空间复杂度均为O(n)。
Code
ArrayList<ArrayList<Integer>> leafPathSum(Node root, int sum){
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> path = new ArrayList<Integer>();
leafPathSumHelper(root, path, result, sum);
return result;
}
void leafPathSumHelper(Node root, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> result, int sum){
if (root == null) return;
path.add(root.value);
if (root.left == null && root.right == null && root.value == sum){
ArrayList<Integer> tp = new ArrayList<Integer>(path);
result.add(tp);
}
leafPathSumHelper(root.left, path, result, sum - root.value);
leafPathSumHelper(root.right, path, result, sum - root.value);
path.remove(path.length()-1);
}