题目描述

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

题解

本题的路径指从树的根节点开始一直到叶节点所经过的节点形成的路径。由于只有前序遍历是先访问根节点，所以使用前序遍历+回溯。

首先定义一个大容器，用于盛放符合要求的路径。然后开始回溯。
回溯函数有两个部分：

1. 首先判断是否满足结束条件，如果满足就将当前路径添加到容器中。
2. 然后遍历可选择的列表（本题的选择列表是当前节点的左右子树），在遍历结束后进行回溯。

最后别忘了，由于题目要求在返回值的list中，数组长度大的数组靠前，因此还要对得到的大容器按照路径的长度进行排序。

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

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
    if (root == null)
        return res;
    BackTrack(root, target, new ArrayList<>(), 0);

    // 定义比较器
    Collections.sort(res, new Comparator<ArrayList<Integer>>() {
        @Override
        public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
            return o2.size() - o1.size();
        }
    });
    return res;
}

public void BackTrack(TreeNode node, int target, ArrayList<Integer> path, int currentSum) {
    currentSum += node.val;
    path.add(node.val);

    // 如果到达叶节点且路径和等于target，则将得到一条符合要求的路径
    if (node.left == null && node.right == null && currentSum == target)
        res.add(new ArrayList<>(path));

    // 如果不是叶节点，那么继续递归遍历它的子节点
    if (node.left != null)
        BackTrack(node.left, target, path, currentSum);
    if (node.right != null)
        BackTrack(node.right, target, path, currentSum);

    // 回溯
    path.remove(path.size()-1);
}