100. Same Tree

解題程式碼

var isSameTree = function (p, q) {
  if (p === null && q === null) return true;

  if ((p === null && q !== null) || (p !== null && q === null) || p.val !== q.val) {
    return false;
  }

  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

解題思路、演算法

這題用 DFS 實作，有幾種狀況可以判斷兩個樹不同:

1. 某一節點是 null 另一節點不是時
2. 兩個節點值不同

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(1)

參考資料

103. Binary Tree Zigzag Level Order Traversal

解題程式碼

var zigzagLevelOrder = function (root) {
  const queue = [root];
  const result = [];
  let layerCounter = 1;

  while (queue[0]) {
    const layerNodesNum = queue.length;
    const layerValues = [];

    for (let i = 0; i < layerNodesNum; i++) {
      let curNode = queue.shift();
      layerValues.push(curNode.val);

      if (curNode.left) queue.push(curNode.left);
      if (curNode.right) queue.push(curNode.right);
    }
    layerCounter % 2 === 0 ? result.push(layerValues.reverse()) : result.push(layerValues);
    layerCounter++;
  }

  return result;
};

解題思路、演算法

解題概念和 LeetCode 102 相當相似。

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(n)

參考資料

437. Path Sum III

解題程式碼

var pathSum = function (root, targetSum) {
  let pathNum = 0;
  const nodeMap = new Map();

  const DFS = (node, curSum) => {
    if (!node) return;
    curSum += node.val;

    if (curSum === targetSum) pathNum++;
    if (nodeMap.get(curSum - targetSum) > 0) pathNum += nodeMap.get(curSum - targetSum);

    if (!nodeMap.has(curSum)) {
      nodeMap.set(curSum, 1);
    } else {
      nodeMap.set(curSum, 1 + nodeMap.get(curSum));
    }

    if (node.left) DFS(node.left, curSum);
    if (node.right) DFS(node.right, curSum);

    nodeMap.set(curSum, nodeMap.get(curSum) - 1);
  };
  DFS(root, 0);

  return pathNum;
};

解題思路、演算法

這題可以使用 DFS + HashMap 來解題。首先用 DFS 搜尋二元樹的各個路徑，並同時將經過路徑的所有節點總和記錄在 HashMap。

例如當前走過了 10 => 5 => 2 => 1 的路徑(綠色線圈起的部分)，hashMap 會有以下鍵值對

{ 10: 1, 15: 1, 17: 1, 18: 1}

此時拿 18 - 8(targetSum) = 10，10 存在於 HashMap 中，就可以知道在這條路徑下有一段路的節點總和為 targetSum，這種是從樹的中間層開始總和為 targetSum 的情況，而另一種 case 是從根節點的總和等於 targetSum 的情況，

有點像是以前遇過的 prefix sum 的概念

而為了避免會重複計算到路徑，當搜尋完回到二元樹的上層節點時，要記得把 hashMap 中的路徑減掉，例如搜尋完回到節點 2，減掉 key 為 18 的路徑一次，回到節點 5，減掉 key 為 17 的路徑一次。

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(n)

參考資料

Path Sum III | Leet code 437 | Theory explained + Python code

贾考博 LeetCode 437. Path Sum III