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

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 sum int整型
     * @return int整型
     */
    // public int FindPath (TreeNode root, int sum) {
    //     // write code here


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

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

    //     if (root == null) {
    //         return 0;
    //     }

    //     FindAllPath(root, totalList, levelList);

    //     for (int i = 0; i < totalList.size(); i++) {
    //         ArrayList<Integer> level = totalList.get(i);
    //         FindTargetPath(level, resultList, sum);

    //         System.out.print("第" + i + "条路径的节点值:");
    //         for (int j = 0; j < level.size(); j++) {
    //             System.out.print(level.get(j) + ",");
    //             //那么，如何从这个数组中，找到连续值之和，为目标数呢？

    //         }
    //         System.out.println();
    //     }

    //     return resultList.size();
    // }

    private void FindTargetPath(ArrayList<Integer> list,
                                ArrayList<ArrayList<Integer>> resultList, int num) {
        int startIndex = 0;
        int endIndex = 0;

        firstLoop:
        for (int i = 0; i < list.size() - 1; i++) {
            //依次从头节点到尾节点，移动开始指针，往后计算，可以做到
            ArrayList<Integer> oneResult = new ArrayList<Integer>();

            int sum = list.get(i);
            oneResult.add(sum);
            for (int j = i + 1; j < list.size(); j++) {

                sum += list.get(j);
                oneResult.add(list.get(j));

                if (sum == num) {
                    //把结果保存下来，并跳出本循环
                    //这里有个难点，如何剔除重复呢？换句话说，需要剔除重复吗？
                    resultList.add(oneResult);
                    continue firstLoop;
                }
            }
        }
    }

    private void FindAllPath(TreeNode node,
                             ArrayList<ArrayList<Integer>> resultList, ArrayList<Integer> levelList) {

        //这题区别于上一题，不要求到叶子节点，而且可以从任一节点开始都行,只要达成和是目标值，就符合条件。

        //上一道题的好处，是每条路径都从根节点触发， 这里难就难在，出发点是不定的。

        //包括叶子节点在内的所有节点，都可以是出发点。

        //那么。该怎么去遍历取出符合的路径呢？

        //欸，可以先把所有的根到叶子路径，组成一个集合，然后从集合中取出某一个路径，从这个路径中取出连续的几个点，能够组成这个和，说明符合路径。

        //问题转化成了，求一个数组中，连续的几个值之和，为目标数的问题。

        //那么，我先找出从根到叶的所有路径，然后遍历这些路径，从每条路径中找出连续的点之和为目标数的情况



        if (node == null) {
            resultList.add(levelList);
            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) {
            FindAllPath(node.left,  resultList, levelListLeft);
        } else {
            FindAllPath(node.left,  resultList, levelListLeft);
            FindAllPath(node.right, resultList, levelListRight);
        }

    }

    //优化一下，在寻找路径的时候，直接做计算，这样可以不用保存路径结果，直接开始路径计数，优化重复计算



    int res = 0;//统计路径数
    public int FindPath (TreeNode root, int sum) {
        if(root == null){
            return 0;
        }

        FindOnePath(root,sum);//寻找从根节点触发的，所有路径数

        FindPath(root.left,sum);//寻找从左节点出发的路径数。
        FindPath(root.right,sum);//寻找从右节点出发的路径数。        
        return res;
    }

    private void FindOnePath(TreeNode node, int num) {
        if (node == null){
            return;
        }

        if(num == node.val){
            res++;
        }

        FindOnePath(node.left, num - node.val);
        FindOnePath(node.right, num - node.val);
    }


}