二叉树中和为某一值的路径

题目描述

• 输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路：

• 1.创建一个ArrayList<ArrayList<integer>>作为最终的返回结果；</integer>

• 2.递归遍历，遍历到叶节点时，将ArrayList<integer>对象加到ArrayList<ArrayList<integer>>集合中，ArrayList<integer>对象应包括从根节点到该叶节点路径的所有节点值；</integer></integer></integer>

• 3.遍历ArrayList<ArrayList<integer>>集合，找出子集合之和等于target的集合；</integer>

• PS：后来发现可以在第2步时候，判断子集合的值是否等于target，等于的话，添加到ArrayList<ArrayList<integer>>集合中，否则不添加，这样就可以直接返回ArrayList<ArrayList<integer>>对象，省去第3步；</integer></integer>

  public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
    ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
    if (root == null) {
        return arrayLists;
    }
    ArrayList<Integer> arrayList = new ArrayList<>();
    findPathHelper(arrayLists, arrayList, root, 0, target);
    return arrayLists;
  }
  
  private void findPathHelper(ArrayList<ArrayList<Integer>> arrayLists, ArrayList<Integer> arrayList, TreeNode root, int count, int target) {
  
    count += root.val;
    arrayList.add(root.val);
    if (root.left != null && root.right != null) {
        // 当根节点的左右节点都不为空时，复制arrayList，因为此时至少对应两条到叶节点的路径
        ArrayList<Integer> arrayList1 = new ArrayList<>();
        arrayList1.addAll(arrayList);
        int target1 = count;
        findPathHelper(arrayLists, arrayList, root.left, count, target);
        findPathHelper(arrayLists, arrayList1, root.right, target1, target);
    } else if (root.left != null) {
        // 当根节点只有左节点的时候
        findPathHelper(arrayLists, arrayList, root.left, count, target);
    } else if (root.right != null) {
        // 当根节点只有右节点时候
        findPathHelper(arrayLists, arrayList, root.right, count, target);
    } else {
        // 叶节点，判断该路径的所有节点的和是否等于target，如果等于加入到arrayLists中，否则不添加
        if (target == count) {
  
            arrayLists.add(arrayList);
        }
    }
  }