二叉樹中和為某一值的路徑

題目描述

輸入一顆二叉樹和一個(gè)整數(shù)，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑。

思路

1. 前序遍歷二叉樹，每次更新當(dāng)前路徑的和curtSum；
2. 判斷當(dāng)前結(jié)點(diǎn)是否是葉子結(jié)點(diǎn)，以及curtSum是否等于expectNumber。如果是，把當(dāng)前路徑保存在res結(jié)果中；
3. 若不符合條件，則彈出此結(jié)點(diǎn)。

實(shí)現(xiàn)代碼

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function FindPath(root, expectNumber) {
    var result = [];
    if (root === null) {
        return result;
    }
    dfsFind(root, expectNumber, [], 0, result);
    return result; 

}
function dfsFind(root, expectNumber, path, currentSum, result) {
    currentSum += root.val;

    path.push(root.val);

    if (currentSum == expectNumber && root.left == null && root.right == null) {
        result.push(path.slice(0)); 
    }
    if (root.left != null) {
        dfsFind(root.left, expectNumber, path, currentSum, result);
    }

    if (root.right != null) {
        dfsFind(root.right, expectNumber, path, currentSum, result);
    }

    path.pop();
}