完賽心得

今年參加鐵人賽，個人感覺是水過一年的感覺XD，因為就只是把解題的練習記錄複製貼上來，但今年因為沒有備太多天的稿，所以在時程的壓力下，的確有達到督促自己多去練題目的動力，所以我覺得是有達到好的效果。

而即使完賽後，在第一天文章提到預計要練習的題目列表中，還有很多沒有練習到，所以我創建了一個 Github Repo，裡面會記錄我未來繼續解其他題目的筆記和解法，都是用 JS 做解題，希望能提供給也是用 JS 刷題的開發者做參考。
JavaScript-leetcode-practice

不想放棄變得更強，所以明年我們會再見的，期待我的新主題吧!

101. Symmetric Tree

解題程式碼

var isSymmetric = function (root) {
  function DFS(left, right) {
    if (left === null && right === null) return true;
    if (left === null || right === null) return false;

    return left.val === right.val && DFS(left.left, right.right) && DFS(left.right, right.left);
  }
  return DFS(root.left, root.right);
};

解題思路、演算法

這題用深度優先搜尋，根節點自己一定對稱，所以另外寫一個函式，取左右子樹去做遞迴

然後考慮以下幾種情況如果成立，就代表沒有對稱:

1. 左子樹根節點有值，右子樹沒有，反之
2. 左子樹當前根節點值和右子樹當前根節點值不同
3. 往下遞迴，用左子樹的左子節點和右子樹的右子節點比較，用左子樹的右子節點和右子樹的左子節點比較，有不同就沒有對稱

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(h)，整個樹的高度

參考資料

https://youtu.be/Mao9uzxwvmc?si=q3sokoHMNeoHAP_b

863. All Nodes Distance K in Binary Tree

解題程式碼

var distanceK = function(root, target, k) {
  const graphMap = new Map();
  const seen = new Set();
  const result = [];
  const queue = [[target.val, 0]];

  const buildGraph = (node, parent) => {
    if (!node) return;
    const neighbor = [];

    if (parent) {
      neighbor.push(parent.val);
    }
    if (node.left) {
      neighbor.push(node.left.val);
      buildGraph(node.left, node);
    }
    if (node.right) {
      neighbor.push(node.right.val);
      buildGraph(node.right, node);
    }
    graphMap.set(node.val, neighbor);
  }
  buildGraph(root, null);

  while (queue.length) {
    const [popNode, pathNum] = queue.shift();
    if (seen.has(popNode)) continue;
    seen.add(popNode);

    if (pathNum === k) result.push(popNode);
    if (pathNum > k) return result;

    for (let node of graphMap.get(popNode)) {
      queue.push([node, pathNum + 1]);
    }
  }

  return result;
};

解題思路、演算法

這題可以將樹轉成圖的形式，將圖的資料存在 hashMap 裡面，以下面的 tree 為範例的話，就是:

{
  3: [5, 1],
  5: [3, 6, 2],
  6: [5],
  2: [5, 7, 4],
  7: [2],
  4: [2],
  1: [3, 0, 8],
  0: [1],
  8: [1]
}

建立好圖後，將 target 節點當作圖的出發點，用 queue 儲存，然後每次從 queue 裡取出節點並透過 hashMap 查表，就能找出鄰近節點，經過 k 路徑所到的節點就都會是題目要的結果。

解法的時間、空間複雜度

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

參考資料

leetcode 中文 | All Nodes Distance K in Binary Tree | Amazon亞馬遜考題 | Leetcode 863 | Python

572. Subtree of Another Tree

解題程式碼

var isSubtree = function(root, subRoot) {
    const isSameTree = (p, q) => {
        if (p === null && q === null) return true;
        if (p === null || q === null || p.val !== q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    if (root === null || subRoot === null) return false;
    if (isSameTree(root, subRoot)) return true;
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
};

解題思路、演算法

這題使用 DFS，去比對當前的 root 是否和 subRoot 相同，是的話返回 true，否就去遞迴當前 root 的左右子樹是否和 subRoot 相同

至於判斷兩個樹是否相同，則可以參考 100. Same Tree 這題。

解法的時間、空間複雜度

n is the number of nodes in the tree rooted at the root.
m is the number of nodes in the tree rooted at subRoot.

時間複雜度: O(m * n)
空間複雜度: O(m + n)

參考資料

https://youtu.be/E36O5SWp-LE?si=6RUh_pk79VRxJeGM