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

作者：神奇的程序員 2022-11-06 19:43:10

按照前序遍歷的順序去訪問這顆二叉樹，在訪問節點10之后，就會訪問節點5。圖中二叉樹并沒有指向父節點的指針，當訪問節點5的時候，我們是不知道前面經過了哪些節點的，此時我們就需要準備一個棧，用來存儲訪問過的節點。

思路分析

我們舉例來做分析，如下圖所示，我們準備了一顆二叉樹和一個整數22，通過觀察后，我們很容易就能看出它有兩條路徑的節點值加起來和為22。

10、5、7
10、12

上述兩個路徑都是從根節點出發到葉子節點的，也就是說路徑總是以根節點為起始點，因此我們首先需要遍歷根節點。在樹的三種遍歷方式中，只有前序遍歷是首先訪問根節點的。

當到達節點5的時候，路徑中包含兩個節點：10、5。接下來遍歷到節點4，我們把這個節點入棧，這時候已經到達葉節點，但棧中的所有節點之和是19。這個和不等于輸入的值22，因此它不符合要求的路徑。

最后，我們要遍歷的節點是12。在遍歷這個節點之前，需要先經過節點5回到節點10。同樣的，每次當從子節點回到父節點的時候，我們都需要在路徑上刪除子節點。最后在節點10到達節點12的時候，路徑上的兩個節點的值之和也是22，因此這也是一條符合要求的路徑。

分析到這里，我們就找到了一些規律：
當用前序遍歷的方式訪問到某一節點時，就把該節點添加到路徑上，并累加該節點的值
如果該節點為葉節點，并且路徑中節點值的和剛好等于輸入的整數，則當前路徑符合要求
如果該節點非葉節點，則繼續訪問它的子節點。從節點路徑棧中刪除當前節點

遞歸上述過程，直至二叉樹的所有節點訪問完畢。

實現代碼

形成了清晰的思路之后，接下來我們就可以輕松的寫出代碼了，如下所示：

聲明需要的變量：已訪問過的路徑棧、滿足預期的路徑數組、當前已訪問節點的值總和
從root節點開始，用前序遍歷訪問所有節點，篩選并存儲滿足預期條件的路徑

  findPath(root: Node<number>, expectedSum: number): Array<string> {
    if (root == null) return [];

    // 用一個棧來存儲訪問過的路徑
    const pathStack = new Stack();
    // 存儲符合條件的路徑
    const pathList: Array<string> = [];
    // 當前已訪問路徑總和
    const currentSum = 0;
    // 從root節點開始搜索節點
    this.searchNode(root, expectedSum, pathStack, currentSum, pathList);
    return pathList;
  }

取出根節點的值，將其進行累加
累加后，將根節點的值壓入路徑棧中
判斷是否訪問到了葉節點，如果為葉節點且當前已訪問的節點路徑總和等于預期條件則將路徑棧中的路徑放入符合條件的路徑數組中
當前節點非葉節點，則繼續遞歸訪問它的左、右子樹
左、右子樹都訪問完成后，則代表當前路徑不滿足預期條件，將其從路徑棧中出棧

private searchNode(
    root: Node<number>,
    expectedSum: number,
    pathStack: Stack,
    currentSum: number,
    pathList: Array<string>
  ) {
    // 累加當前已訪問節點的和，將當前節點入棧
    currentSum += root.key;
    pathStack.push(root.key);

    // 如果是葉節點，并且路徑上節點值的和等于輸入的值，則存儲當前路徑棧中的節點
    const isLeaf = root.left == null && root.right == null;
    if (currentSum == expectedSum && isLeaf) {
      pathList.push(pathStack.toString());
    }
    // 非葉子節點，則遍歷它的子節點
    if (root.left != null) {
      this.searchNode(root.left, expectedSum, pathStack, currentSum, pathList);
    }
    if (root.right != null) {
      this.searchNode(root.right, expectedSum, pathStack, currentSum, pathList);
    }

    // 當前節點不符合條件，將其出棧
    pathStack.pop();
  }

測試用例

接下來我們用文章開頭的例子來測試下上述代碼能否正確執行。

const tree: Node<number> = {
  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);

如下所示，成功得計算出了兩條路徑。

我們將節點12改成20，再來測試下，結果如下所示，只有一條路徑符合預期。

示例代碼

本文用到的代碼完整版請移步：

TreeOperate.ts
TreeOperate-test.ts

責任編輯：武曉燕來源：神奇的程序員

二叉樹指針節點