[Easy] 判斷二叉樹是否相同 Same Tree

判斷二叉樹是否相同 Same Tree，是程式面試中，很常會考的入門考題，Leetcode 中有很多題目有需要用到此概念，最基本的題目是 Leetcode 100. Same Tree，以下我們要介紹實際作法。

可以看到，下面的二叉樹 1 與 二叉樹 2 是相同的，但是二叉樹 3 與二叉樹 4 是不同的

    二叉樹 1        二叉樹 2
      1               1
     / \             / \
    2   3           2   3

    二叉樹 3        二叉樹 4
      2               2
     / \             / \
    3   4           4   3

要怎麼判斷兩個二叉樹是否相同呢? 我們可以用遞迴 Recursion 來做到

// 先比較根節點
      1               1

// 遞迴比較左邊的子節點
      1              1
     /              /
    2              2

// 遞迴比較右邊的子節點
     1               1
      \               \
       3               3

判斷二叉樹是否相同程式碼

function isSameTree(p, q) {
  // 如果沒有左邊的子節點，也沒有右邊的，表示兩者都是空，所以相同，回傳 true
  if (!p && !q) return true;

  // 如果通過上面的檢查，代表至少一個不為空，
  // 因此，這時候如果有一個為空，代表一個為空，一個不為空
  // 兩者不同，所以回傳 false
  if (!p || !q) return false;

  // 接著確認，左右兩邊都有值的狀況，這時如果兩者的值不同，就回傳 false
  if (p.val !== q.val) return false;

  // 最後只需要遞迴的比較左邊的子樹，以及右邊的子樹，就大功告成了
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}