376. Binary Tree Path Sum
Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target.
A valid path is from root node to any of the leaf nodes.
Example
Example 1:
Input:
{1,2,4,2,3}
5
Output: [[1, 2, 2],[1, 4]]
Explanation:
The tree is look like this:
1
/ \
2 4
/ \
2 3
For sum = 5 , it is obviously 1 + 2 + 2 = 1 + 4 = 5
Example 2:
Input:
{1,2,4,2,3}
3
Output: []
Explanation:
The tree is look like this:
1
/ \
2 4
/ \
2 3
Notice we need to find all paths from root node to leaf nodes.
1 + 2 + 2 = 5, 1 + 2 + 3 = 6, 1 + 4 = 5
There is no one satisfying it.
思路：
递归法，用helper方法，可以传更多参数
注意：
代码：
/*
* @param root: the root of binary tree
* @param target: An integer
* @return: all valid paths
*/
public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
List<List<Integer>> result = new ArrayList<>();
ArrayList<Integer> path = new ArrayList<>(); if (root == null) {
return result;
}
path.add(root.val);
helper(root, path, root.val, target, result);
return result;
} public void helper (TreeNode root,
ArrayList<Integer> path,
int sum,
int target,
List<List<Integer>> result) {
//meet leaf
if (root.right == null && root.left == null) {
if (sum == target) {
result.add(new ArrayList(path));
}
return;
}
// right node
if (root.right != null) {
path.add(root.right.val);
helper(root.right, path, sum + root.right.val, target, result);
path.remove(path.size() - 1);
}
//left node
if (root.left != null) {
path.add(root.left.val);
helper(root.left, path, sum + root.left.val, target, result);
path.remove(path.size() - 1);
}
}