Leetcode 113) Path Sum II

28 Sep 2021 in Algorithms

My Answer

/**
 * 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 {
    List<List<Integer>> res;

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        res=new ArrayList<List<Integer>>();
        if(root==null){return res;}
        List<Integer> prev= new ArrayList<Integer>();
        helper(targetSum,prev,root);
        return res ;
    }

    //helper function, will return targetSum, 
    public void helper(int target, List<Integer> prev , TreeNode tn){
        target-=tn.val;       
        prev.add(tn.val);
        List<Integer> prev2= new ArrayList<>(prev);

        //base case : if it's a leaf node
        if(tn.right==null && tn.left==null){
            if(target==0){
                res.add(prev);
            }
            return;
        }
        if(tn.left!=null){
            helper(target,prev,tn.left);            
        }
        if(tn.right!=null){
            helper(target,prev2,tn.right);
        }
    }

}

Other Answer

/**
 * 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>> list = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        pathSum(root, targetSum, list,temp);
        return list;
    }

    private void pathSum(TreeNode node, int Sum, List<List<Integer>> list,List<Integer> temp){
        // List<Integer> temp = new ArrayList<>();
        if(node == null)
            return;

        temp.add(node.val);
        if(node.left == null && node.right == null && Sum - node.val == 0){
            list.add(new ArrayList<>(temp));
            temp.remove(temp.size()-1);
            return;
        }else{
            pathSum(node.left, Sum - node.val, list,temp);
            pathSum(node.right, Sum - node.val, list,temp);
        }
        temp.remove(temp.size()-1);
    }
}

arraylist 다루는 법, 더 잘 알면 좋다.