快捷導(dǎo)航

JavaScript算法實(shí)例之求二叉樹從根到葉的所有路徑和

更新時(shí)間：2023年10月26日 09:49:30 作者：ysheep

如果你希望求某一特定路徑（例如從根到葉子）上數(shù)字的和,那么問題就轉(zhuǎn)變?yōu)榱恕扒蠖鏄鋸母饺~的所有路徑和”,所以本文給大家介紹了如何使用JavaScript求二叉樹從根到葉的所有路徑和,需要的朋友可以參考下

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function sumPaths(node, currentSum = 0) {
  if (!node) return 0;

  currentSum = currentSum * 10 + node.value;

  // 如果是葉子節(jié)點(diǎn)，直接返回當(dāng)前和
  if (!node.left && !node.right) return currentSum;

  // 否則返回左右子樹的和
  return sumPaths(node.left, currentSum) + sumPaths(node.right, currentSum);
}

// 使用上面的樹作為示例
const root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(8);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(7);
root.right.right = new TreeNode(9);

console.log(sumPaths(root)); // 輸出: 2241

深度優(yōu)先搜索（Deep First Search，簡稱 DFS）是一種用于遍歷或搜索樹或圖的算法。在樹或圖上進(jìn)行搜索的過程中，DFS 盡可能沿著分支深入到樹或圖的盡頭，然后再回溯至其他分支繼續(xù)探索，直到已經(jīng)訪問過所有可能的路徑。

工作原理：

從起始節(jié)點(diǎn)開始。
探索盡可能深的分支。
如果當(dāng)前節(jié)點(diǎn)沒有未探索的分支，則回溯。
探索下一個(gè)分支。
重復(fù)以上步驟，直到訪問所有的節(jié)點(diǎn)。

實(shí)現(xiàn)：

DFS 可以通過遞歸或使用堆棧實(shí)現(xiàn)。

遞歸實(shí)現(xiàn)：

在樹的情況下，可以遞歸地訪問每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)。

function dfs(node) {
  if (node == null) return;

  console.log(node.value);  // 處理當(dāng)前節(jié)點(diǎn)
  dfs(node.left);  // 遞歸訪問左子節(jié)點(diǎn)
  dfs(node.right);  // 遞歸訪問右子節(jié)點(diǎn)
}

使用堆棧實(shí)現(xiàn)：

堆棧可以幫助保存待訪問的節(jié)點(diǎn)。一般在圖中使用堆棧實(shí)現(xiàn) DFS，因?yàn)閳D可能含有循環(huán)，需要一個(gè)額外的數(shù)據(jù)結(jié)構(gòu)來跟蹤已訪問的節(jié)點(diǎn)。

function dfs(graph, start) {
  let stack = [];
  let visited = new Set();

  stack.push(start);

  while (stack.length) {
    let node = stack.pop();
    if (!visited.has(node)) {
      console.log(node);  // 處理當(dāng)前節(jié)點(diǎn)
      visited.add(node);

      // 添加未訪問的鄰接節(jié)點(diǎn)到堆棧
      for (let neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
          stack.push(neighbor);
        }
      }
    }
  }
}