题解 | #二叉树中和为某一值的路径(二)#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param target int整型
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> FindPath (TreeNode root, int target) {
        // write code here

        //二叉树的遍历，如果借助辅助空间，一般使用队列或者栈。看需要，队列就是分层遍历，栈就是前中后序遍历

        //这个问题，可以退化成，链表之和为targetNumber的问题，链表就是这棵树从根到叶子，能发展多少条链表

        //是不是按照中序遍历，把这个链表结合起来，但是展开成链表，还是需要递归的，不如直接在递归的过程中，把结果算一下，如果有问题，直接就丢弃了，没问题的路径保留，最后就可以直接返回结果了。

        ArrayList<ArrayList<Integer>> resultList = new ArrayList<ArrayList<Integer>>();

        ArrayList<Integer> levelList = new ArrayList<Integer>();

        if(root == null){
            return resultList;
        }

        FindSubPath(root, target, resultList, levelList);

        return resultList;
    }

    private void FindSubPath(TreeNode node, int target,
                             ArrayList<ArrayList<Integer>> resultList, ArrayList<Integer> levelList) {
        // TODO
        if (node == null && target == 0) {
            resultList.add(levelList);
            return;
        }

        if (node == null && target != 0) {
            //说明次路径不符合。需要丢弃。如何丢弃呢？不往resultList里添加嘛
            return;
        }

        ArrayList<Integer> levelListLeft = new ArrayList<Integer>();
        levelListLeft.addAll(levelList);
        ArrayList<Integer> levelListRight = new ArrayList<Integer>();
        levelListRight.addAll(levelList);

        levelListLeft.add(node.val);
        levelListRight.add(node.val);

        //这里要区别一下叶子节点和普通节点，叶子节点，左右子节点都为null，如果这样写，会+两遍集合进去，因此当叶子节点时，要剔除一次！

        if (node.left == null && node.right == null) {
            FindSubPath(node.left, target - node.val, resultList, levelListLeft);
        } else {
            FindSubPath(node.left, target - node.val, resultList, levelListLeft);
            FindSubPath(node.right, target - node.val, resultList, levelListRight);
        }

    }
}