題目描述

輸入一顆二叉樹的跟節(jié)點(diǎn)和一個(gè)整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑。(注意: 在返回值的list中，數(shù)組長(zhǎng)度大的數(shù)組靠前)

題解

本題的路徑指從樹的根節(jié)點(diǎn)開始一直到葉節(jié)點(diǎn)所經(jīng)過(guò)的節(jié)點(diǎn)形成的路徑。由于只有前序遍歷是先訪問(wèn)根節(jié)點(diǎn)，所以使用前序遍歷+回溯。

首先定義一個(gè)大容器，用于盛放符合要求的路徑。然后開始回溯。
回溯函數(shù)有兩個(gè)部分：

1. 首先判斷是否滿足結(jié)束條件，如果滿足就將當(dāng)前路徑添加到容器中。
2. 然后遍歷可選擇的列表（本題的選擇列表是當(dāng)前節(jié)點(diǎn)的左右子樹），在遍歷結(jié)束后進(jìn)行回溯。

最后別忘了，由于題目要求在返回值的list中，數(shù)組長(zhǎng)度大的數(shù)組靠前，因此還要對(duì)得到的大容器按照路徑的長(zhǎng)度進(jìn)行排序。

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);

    // 如果到達(dá)葉節(jié)點(diǎn)且路徑和等于target，則將得到一條符合要求的路徑
    if (node.left == null && node.right == null && currentSum == target)
        res.add(new ArrayList<>(path));

    // 如果不是葉節(jié)點(diǎn)，那么繼續(xù)遞歸遍歷它的子節(jié)點(diǎn)
    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);
}