113. Path Sum II

package LeetCode_113

/**
 * 113. Path Sum II
 * https://leetcode.com/problems/path-sum-ii/description/
 * Given a binary tree and a sum, find all root-to-leaf paths where each path‘s sum equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
5
/  4    8
/   /  11  13   4
/ \     / 7 2    5   1

Return:
[
[5,4,11,2],
[5,8,4,5]
]
 * */

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    val result = ArrayList<List<Int>>()
    fun pathSum(root: TreeNode?, sum: Int): List<List<Int>> {
        if (root == null) {
            return result
        }
        dfsWithList(root, ArrayList(), 0, sum)
        return result
    }

    private fun dfsWithList(root: TreeNode?, list: ArrayList<Int>, currentSum: Int, target: Int) {
        if (root==null){
            return
        }
        list.add(root.`val`)
        if (root.left == null && root.right == null) {
            if (currentSum+root.`val`==target){
                result.add(ArrayList<Int>(list))
            }
        }
        dfsWithList(root.left,list,currentSum+root.`val`,target)
        dfsWithList(root.right,list,currentSum+root.`val`,target)
        //because is backtracking, so need reset the list for next result
        list.removeAt(list.size-1)
    }
}