Leetcode Path Sum II

题目名称：113 Path Sum II

难度：Medium

知识点：Recursion

解题思路：

这道题还是利用二叉树组的特性进行recursion求解。首先判断根节点是否为null，再判断左结点和右结点，他们两个的目标值都是原始值减去根节点的值，对于这两个子结点的子节点，recursion中传入的已经减掉根节点的目标值再减去他们各自作为根节点的值就可以了。还有一个注意的点是，我们可以一直root.left root.right定位到他们的子节点，但是此题是要返回正确的path的node的值组成的数组，这样的话，我们肯定需要新建立一个暂时数组来track路径上经历的值，既然我们只有一个数组来track，那我们肯定就要删除last index上的值达到回退的效果，需要回退的情况有两种，在我们达到叶子结点之后，检查完叶子结点之后需要删除掉，第二种情况是针对非叶子结点，在我们检查完一个中间节点的左右结点后，应该删除该中间结点，因为她已经不回参与到后面的path计算中。

Java 代码如下：

class Solution {
    public List> pathSum(TreeNode root, int targetSum) {
        List> result = new ArrayList>();
        List temp = new ArrayList();
        findPath(root, targetSum, result, temp);
        return result; 
    }
    
    public void findPath(TreeNode root, int target, List>result, List temp){
        if(root == null) return;
        temp.add(root.val);
        if(root.left == null && root.right == null){
            if(target == root.val){
                result.add(new ArrayList(temp));
            }
            temp.remove(temp.size()-1);
            return;
        }  
        findPath(root.left, target-root.val, result, temp);
        findPath(root.right, target-root.val, result, temp);
        temp.remove(temp.size()-1);
    }
}