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);
    }
}