Binary Tree Path Sum III

首先，样例的答案是：[[2,1,3],[2,4],[3,1,2],[4,2]]。（中文版面有问题，已反馈）
1.首先，我们观察样例，发现相同的路径点，走的顺序不一样，就视为不同的路径；同一个点，只能走一次，不能重复走。
2.既然这样，那我们就有一个最简单的思路，枚举树上的点，以该点为起点搜索可行的路径。
3.dfs(root, target, results)：遍历整棵二叉树，当前遍历到的点是root。
目标值为target，所有可行路径存储在results中。
4.findSum(root, father, target, path, results);
搜索以root为起点，目标值为target的可行路径，并将搜索路径存储在path中。当target为0时，即代表该搜索路径为一条可行路径，将其存入答案results中。
当root为路径起点时，father为空，此时可以向三个方向进行搜索（父亲节点、左儿子节点、右儿子节点）。
当root不是路径起点时，此时的father为搜索路径中，root的上一个点，只能向三个方向中，非father的两个方向进行搜索。
5.最后要注意的就是数据的问题了，题上并没有说数据都是正整数，所以是有可能存在负值和0的。
/**
 * Definition of ParentTreeNode:
 * 
 * class ParentTreeNode {
 *     public int val;
 *     public ParentTreeNode parent, left, right;
 * }
 */
public class Solution {
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    public List<List<Integer>> binaryTreePathSum3(ParentTreeNode root, int target) {
        /**这道题相当于从任何一个节点出发，找到target的路径输出
         * 从root遍历左右子树的每个点，从每个点出发找到为target的路径*/
         List<List<Integer>> results = new ArrayList<>();
         

         dfs(root,results,target);
         return results;
    }
    public void dfs(ParentTreeNode root, List<List<Integer>> results, int target) {
        
        if (root == null) {
            return;
        }
        
        List<Integer> buffer = new ArrayList<>();
        findSum(root, null, target,results, buffer);
        
        dfs(root.left, results, target);
        dfs(root.right, results, target);
    }
    
    private void findSum(ParentTreeNode root, ParentTreeNode from, int target, 
    List<List<Integer>> results, List<Integer> buffer ){
        if(root == null){
            return;
        }

        buffer.add(root.val);
        target = target - root.val;
        if (target == 0) {
            results.add(new ArrayList<>(buffer));
        }
        if(root.parent != null && root.parent !=from){
            findSum(root.parent, root, target, results, buffer);
        }
        if(root.left !=null && root.left !=from){
            findSum(root.left, root, target, results, buffer);
        }
        if(root.right !=null && root.right !=from){
            findSum(root.right, root, target, results, buffer);
        }
        buffer.remove(buffer.size()-1);
    }
}