二叉樹中和為某一值的路徑
題目描述
輸入一顆二叉樹和一個(gè)整數(shù)虽画，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑期升。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑灵妨。
思路
- 前序遍歷二叉樹况脆，每次更新當(dāng)前路徑的和curtSum；
- 判斷當(dāng)前結(jié)點(diǎn)是否是葉子結(jié)點(diǎn)农猬，以及curtSum是否等于expectNumber却音。如果是改抡，把當(dāng)前路徑保存在res結(jié)果中；
- 若不符合條件系瓢，則彈出此結(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();
}
