6ms Java solution, easy to understand


  • 1
    Y

    Every time we pass a node, we deduct the node's value from the sum. Once the remaining equals 0 and this node has no children, we add the path to the result.

    List<List<Integer>> res;
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        res = new ArrayList<>();
        if(root == null){
            return res;
        }
        List<Integer> temp = new ArrayList<>();
        temp.add(root.val);
        helper(root, sum, temp);
        return res;
    }
    
    private void helper(TreeNode root, int remain, List<Integer> temp){
        remain -= root.val;
        if(remain == 0 && root.left == null && root.right == null){
            res.add(temp);
        }else if(remain != 0 && root.left == null && root.right == null){
            return;
        }
        
        if(root.left != null){
            List<Integer> leftSub = new ArrayList<>(temp);
            leftSub.add(root.left.val);
            helper(root.left, remain, leftSub);
        }
        
        if(root.right != null){
            List<Integer> rightSub = new ArrayList<>(temp);
            rightSub.add(root.right.val);
            helper(root.right, remain, rightSub);
        }
    }

  • 0
    J

    Brilliant solution! Very clear and easy to understand.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.