113. Path Sum II

三刷 06/2022

Time O(N^2) -> O(N) time to copy the path and performs O(N) times -> N is #nodes

Space O(N)

Runtime: 2 ms, faster than 73.40% of Java online submissions for Path Sum II.

Memory Usage: 44.9 MB, less than 31.29% of Java online submissions for Path Sum II.

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode() {}

 *     TreeNode(int val) { this.val = val; }

 *     TreeNode(int val, TreeNode left, TreeNode right) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

class Solution {

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {

        List<List<Integer>> result = new ArrayList<>();

        dfs(root, targetSum, new ArrayList<>(), result);

        return result;

    }

    

    private void dfs(TreeNode node, int targetSum, List<Integer> path, List<List<Integer>> result) {

        if (node == null) {

            return;

        }

        targetSum -= node.val;

        path.add(node.val);

        if (node.left == null && node.right == null) {

            if (targetSum == 0) {

                result.add(new ArrayList<>(path));

            }

            path.remove(path.size() - 1);

            return;

        }

        dfs(node.left, targetSum, path, result);

        dfs(node.right, targetSum, path, result);

        path.remove(path.size() - 1);

    }

}

二刷
100.00 % 
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        if (root != null) {
            helper(root, sum, new ArrayList<>(), result);
        }
        return result;
    }
    private void helper(TreeNode node, int sum, List<Integer> path, List<List<Integer>> result) {
        path.add(node.val);
        if (node.left == null && node.right == null) {
            if (sum == node.val) {
                result.add(new ArrayList<>(path));
            }
        } else {
            if (node.left != null) {
                helper(node.left, sum - node.val, path, result);
             }
            if (node.right != null) {
                helper(node.right, sum - node.val, path, result);
            }
        }
        path.remove(path.size() - 1);
    }
}
一刷
 46.45 %
public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
     
        pathSumHelper(root, sum, new ArrayList<>(), result);
        return result;
    }
    private void pathSumHelper(TreeNode root, int sum, List<Integer> path, List<List<Integer>> result) {
        if (root == null) return;
        path.add(root.val);
        if (root.left == null && root.right == null && root.val == sum) {
            result.add(new ArrayList<Integer>(path));
        } else {
            pathSumHelper(root.left, sum - root.val, path, result);
            pathSumHelper(root.right, sum - root.val, path, result);
        }
        path.remove(path.size() - 1);
    }
}