113.Path-Sum-II

113. Path Sum II

题目地址

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]
]

代码

Approach #1 Backtracking

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> pathNodes = new ArrayList<Integer>();
        dfs(root, sum, pathNodes,  ans);
        return  ans;        
    }

    private void dfs(TreeNode node, int remainingSum, List<Integer> pathNodes, List<List<Integer>> pathsList) {
        if (node == null)     return;

        pathNodes.add(node.val);
        // Check if the current node is a leaf and also, if it
        // equals our remaining sum. If it does, we add the path to
        // our list of paths
        if (remainingSum == node.val && node.left == null && node.right == null) {
            pathsList.add(new ArrayList<>(pathNodes));
        } else {
            // Else, we will recurse on the left and the right children
            dfs(node.left, remainingSum - node.val, pathNodes, pathsList);
            dfs(node.right, remainingSum - node.val, pathNodes, pathsList);
        }
        // We need to pop the node once we are done processing ALL of it's
        // subtrees.
        pathNodes.remove(pathNodes.size() - 1);
    }
}