package com.app.main.LeetCode.tree;
import com.app.main.LeetCode.base.TreeNode;
import java.util.ArrayList;
import java.util.List;
/**
* 113
*
* medium
*
* https://leetcode.com/problems/path-sum-ii/
*
* 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]
* ]
* Accepted
*
* Created with IDEA
* author:Dingsheng Huang
* Date:2019/11/1
* Time:下午3:46
*/
public class PathSumII {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
backtrack(result, new ArrayList<>(), root, sum, 0);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> path, TreeNode root, int sum, int curr) {
path.add(root.val);
curr += root.val;
// curr node is a leaf
if (root.left == null && root.right == null) {
if (sum == curr) {
result.add(new ArrayList<>(path));
}
return;
}
if (root.left != null) {
backtrack(result, path, root.left, sum, curr);
// backtrack
path.remove(path.size() - 1);
}
if (root.right != null) {
backtrack(result, path, root.right, sum, curr);
// backtrack
path.remove(path.size() - 1);
}
}
}
