113. Path Sum II

Link

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

標準的backtracking列舉所有可能性

  public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> ret = new LinkedList<>();
        if(root == null) return ret;
        helper(root, new LinkedList<Integer>(), ret, sum);
        return ret;
    }
    
    public void helper(TreeNode node, List<Integer> temp, List<List<Integer>> finalRet, int sum){
        if(node.right == null && node.left == null && node.val == sum){
            temp.add(node.val);
            finalRet.add(new ArrayList<>(temp));
            temp.remove(temp.size()-1);
        }
        if(node.right != null){
            temp.add(node.val);
            helper(node.right, temp, finalRet, sum-node.val);
            temp.remove(temp.size()-1);
        }
        if(node.left != null){
            temp.add(node.val);
            helper(node.left, temp, finalRet, sum-node.val);
            temp.remove(temp.size()-1);
        }
    }