Leetcode 113 Path Sum II

思路

思路：首先对树进行前序遍历，在遍历的同时将路径、路径和都记录下来，然后在叶子节点的地方进行判断当前路径和与要求是否匹配，若匹配则将当前路径添加到list中。在一个节点遍历完了之后，需要将当前节点从临时路径tmp中删除。

复杂度分析

时间复杂度O(n)

空间复杂度O(n)

代码

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        // the 2rd time
        List<List<Integer>> res = new ArrayList<>();
        if(root == null)
            return res;
        List<Integer> tmp = new ArrayList<>();
        preorder(res,tmp,root,sum);
        return res;
    }
    
    public void preorder(List<List<Integer>> res,List<Integer> tmp,
                        TreeNode root,int sum){
        // base case:
        if(root == null)
            return;
        tmp.add(root.val);
        // if the current node is a leaf and the sum is satisfied
        if(root.left == null && root.right == null && sum == root.val){
            res.add(new ArrayList<>(tmp));
        }
        preorder(res,tmp,root.left,sum-root.val);
        preorder(res,tmp,root.right,sum-root.val);
        tmp.remove(tmp.size()-1);
    }
}