建站
咨詢
售后
建站咨詢
新聞中心
思路分析
我們舉例來(lái)做分析，如下圖所示，我們準(zhǔn)備了一顆二叉樹(shù)和一個(gè)整數(shù)22，通過(guò)觀察后，我們很容易就能看出它有兩條路徑的節(jié)點(diǎn)值加起來(lái)和為22。
成都創(chuàng)新互聯(lián)專注于企業(yè)營(yíng)銷型網(wǎng)站、網(wǎng)站重做改版、天涯網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5頁(yè)面制作、商城網(wǎng)站建設(shè)、集團(tuán)公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)公司、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁(yè)設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為天涯等各大城市提供網(wǎng)站開(kāi)發(fā)制作服務(wù)。
- 10、5、7
- 10、12
上述兩個(gè)路徑都是從根節(jié)點(diǎn)出發(fā)到葉子節(jié)點(diǎn)的，也就是說(shuō)路徑總是以根節(jié)點(diǎn)為起始點(diǎn)，因此我們首先需要遍歷根節(jié)點(diǎn)。在樹(shù)的三種遍歷方式中，只有前序遍歷是首先訪問(wèn)根節(jié)點(diǎn)的。
按照前序遍歷的順序去訪問(wèn)這顆二叉樹(shù)，在訪問(wèn)節(jié)點(diǎn)10之后，就會(huì)訪問(wèn)節(jié)點(diǎn)5。圖中二叉樹(shù)并沒(méi)有指向父節(jié)點(diǎn)的指針，當(dāng)訪問(wèn)節(jié)點(diǎn)5的時(shí)候，我們是不知道前面經(jīng)過(guò)了哪些節(jié)點(diǎn)的，此時(shí)我們就需要準(zhǔn)備一個(gè)棧，用來(lái)存儲(chǔ)訪問(wèn)過(guò)的節(jié)點(diǎn)。
當(dāng)?shù)竭_(dá)節(jié)點(diǎn)5的時(shí)候，路徑中包含兩個(gè)節(jié)點(diǎn)：10、5。接下來(lái)遍歷到節(jié)點(diǎn)4，我們把這個(gè)節(jié)點(diǎn)入棧，這時(shí)候已經(jīng)到達(dá)葉節(jié)點(diǎn)，但棧中的所有節(jié)點(diǎn)之和是19。這個(gè)和不等于輸入的值22，因此它不符合要求的路徑。
最后，我們要遍歷的節(jié)點(diǎn)是12。在遍歷這個(gè)節(jié)點(diǎn)之前，需要先經(jīng)過(guò)節(jié)點(diǎn)5回到節(jié)點(diǎn)10。同樣的，每次當(dāng)從子節(jié)點(diǎn)回到父節(jié)點(diǎn)的時(shí)候，我們都需要在路徑上刪除子節(jié)點(diǎn)。最后在節(jié)點(diǎn)10到達(dá)節(jié)點(diǎn)12的時(shí)候，路徑上的兩個(gè)節(jié)點(diǎn)的值之和也是22，因此這也是一條符合要求的路徑。
- 分析到這里，我們就找到了一些規(guī)律：
- 當(dāng)用前序遍歷的方式訪問(wèn)到某一節(jié)點(diǎn)時(shí)，就把該節(jié)點(diǎn)添加到路徑上，并累加該節(jié)點(diǎn)的值
- 如果該節(jié)點(diǎn)為葉節(jié)點(diǎn)，并且路徑中節(jié)點(diǎn)值的和剛好等于輸入的整數(shù)，則當(dāng)前路徑符合要求
- 如果該節(jié)點(diǎn)非葉節(jié)點(diǎn)，則繼續(xù)訪問(wèn)它的子節(jié)點(diǎn)。從節(jié)點(diǎn)路徑棧中刪除當(dāng)前節(jié)點(diǎn)
遞歸上述過(guò)程，直至二叉樹(shù)的所有節(jié)點(diǎn)訪問(wèn)完畢。
實(shí)現(xiàn)代碼
形成了清晰的思路之后，接下來(lái)我們就可以輕松的寫出代碼了，如下所示：
- 聲明需要的變量：已訪問(wèn)過(guò)的路徑棧、滿足預(yù)期的路徑數(shù)組、當(dāng)前已訪問(wèn)節(jié)點(diǎn)的值總和
- 從root節(jié)點(diǎn)開(kāi)始，用前序遍歷訪問(wèn)所有節(jié)點(diǎn)，篩選并存儲(chǔ)滿足預(yù)期條件的路徑
findPath(root: Node, expectedSum: number): Array {
if (root == null) return [];
// 用一個(gè)棧來(lái)存儲(chǔ)訪問(wèn)過(guò)的路徑
const pathStack = new Stack();
// 存儲(chǔ)符合條件的路徑
const pathList: Array= [];
// 當(dāng)前已訪問(wèn)路徑總和
const currentSum = 0;
// 從root節(jié)點(diǎn)開(kāi)始搜索節(jié)點(diǎn)
this.searchNode(root, expectedSum, pathStack, currentSum, pathList);
return pathList;
}
- 取出根節(jié)點(diǎn)的值，將其進(jìn)行累加
- 累加后，將根節(jié)點(diǎn)的值壓入路徑棧中
- 判斷是否訪問(wèn)到了葉節(jié)點(diǎn)，如果為葉節(jié)點(diǎn)且當(dāng)前已訪問(wèn)的節(jié)點(diǎn)路徑總和等于預(yù)期條件則將路徑棧中的路徑放入符合條件的路徑數(shù)組中
- 當(dāng)前節(jié)點(diǎn)非葉節(jié)點(diǎn)，則繼續(xù)遞歸訪問(wèn)它的左、右子樹(shù)
- 左、右子樹(shù)都訪問(wèn)完成后，則代表當(dāng)前路徑不滿足預(yù)期條件，將其從路徑棧中出棧
private searchNode(
root: Node,
expectedSum: number,
pathStack: Stack,
currentSum: number,
pathList: Array
) {
// 累加當(dāng)前已訪問(wèn)節(jié)點(diǎn)的和，將當(dāng)前節(jié)點(diǎn)入棧
currentSum += root.key;
pathStack.push(root.key);
// 如果是葉節(jié)點(diǎn)，并且路徑上節(jié)點(diǎn)值的和等于輸入的值，則存儲(chǔ)當(dāng)前路徑棧中的節(jié)點(diǎn)
const isLeaf = root.left == null && root.right == null;
if (currentSum == expectedSum && isLeaf) {
pathList.push(pathStack.toString());
}
// 非葉子節(jié)點(diǎn)，則遍歷它的子節(jié)點(diǎn)
if (root.left != null) {
this.searchNode(root.left, expectedSum, pathStack, currentSum, pathList);
}
if (root.right != null) {
this.searchNode(root.right, expectedSum, pathStack, currentSum, pathList);
}
// 當(dāng)前節(jié)點(diǎn)不符合條件，將其出棧
pathStack.pop();
}
測(cè)試用例
接下來(lái)我們用文章開(kāi)頭的例子來(lái)測(cè)試下上述代碼能否正確執(zhí)行。
const tree: Node= {
key: 10,
left: {
key: 5,
left: {
key: 4
},
right: {
key: 7
}
},
right: {
key: 12
}
};
const targetVal = 22;
const resultPath = treeOperateTest.findPath(tree, targetVal);
console.log(resultPath);
如下所示，成功得計(jì)算出了兩條路徑。
我們將節(jié)點(diǎn)12改成20，再來(lái)測(cè)試下，結(jié)果如下所示，只有一條路徑符合預(yù)期。
示例代碼
本文用到的代碼完整版請(qǐng)移步：
- TreeOperate.ts
- TreeOperate-test.ts
標(biāo)題名稱：二叉樹(shù)中和為某一值的路徑
文章網(wǎng)址：http://fisionsoft.com.cn/article/djcpihi.html
