LCR 153. 二叉樹中和為目標(biāo)值的路徑

LCR 153. 二叉樹中和為目標(biāo)值的路徑

參考題解

前言

該題考察二叉樹中的回溯，使用先序遍歷以及路徑記錄

先序遍歷：根左右

路徑記錄：通過一個(gè)“中間人”（path）來記錄當(dāng)前的路徑和，當(dāng)符合目標(biāo)條件就賦值給res

遞歸函數(shù)–recur()

1、邊界條件

• root為空的時(shí)候，直接返回

2、把root.val加入到path中，同時(shí)還要對(duì)tar減去root.val，即tar -= root.val

3、當(dāng)root是葉子節(jié)點(diǎn)，而且目標(biāo)值tar等于 0 的時(shí)候，即這一條path是符合題目要求的，將path加入到res當(dāng)中

• 注意：這里將path加入到res需要新建一個(gè)對(duì)象，再加入到res中，否則會(huì)有數(shù)據(jù)沖突，后續(xù)path發(fā)生改變的時(shí)候，res中的path也會(huì)有改變，因?yàn)樵?code>path變量始終都是同一個(gè)對(duì)象，在堆中的地址是一樣的，因?yàn)椴判枰陆ㄒ粋€(gè)對(duì)象再加入到res中

4、遞歸遍歷左，右子樹

5、由于已經(jīng)遍歷到了葉子節(jié)點(diǎn)，因此需要進(jìn)行回溯，即path.pop()

public void recur(TreeNode root, int tar) {
    if(root == null) {
        return;
    }
    path.add(root.val); // 加入當(dāng)前節(jié)點(diǎn)值到 path
    tar -= root.val;
    if(tar == 0 && root.left == null && root.right == null) {
        res.add(new LinkedList<>(path));
    }
    recur(root.left, tar);
    recur(root.right, tar);
    path.removeLast();
}

pathTarget函數(shù)

執(zhí)行遞歸函數(shù)recur()

返回res

注意：path和res需要定義為全局變量

public List<List<Integer>> pathTarget(TreeNode root, int target) {
    recur(root, target);
    return res;
}

完整代碼展示

class Solution {
    private final List<List<Integer>> res = new LinkedList<>();
    private final List<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        recur(root, target);
        return res;
    }

    public void recur(TreeNode root, int tar) {
        if(root == null) {
            return;
        }
        path.add(root.val); // 加入當(dāng)前節(jié)點(diǎn)值到 path
        tar -= root.val;
        if(tar == 0 && root.left == null && root.right == null) {
            res.add(new LinkedList<>(path));
        }
        recur(root.left, tar);
        recur(root.right, tar);
        path.removeLast();
    }
}

ps：該題的一些思想和全排列有些相似