LeetCode 100. Same Tree

題目

LeetCode 100. Same Tree

給定兩棵 Binary Tree p 和 q，判斷這兩棵是否為相同的 Tree（每個節點位置、數值都相同）。

原題敘述

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

例子

p 1    q 1
 / \    / \
2   3  2   3
Input: p = [1,2,3], q = [1,2,3]
Output: true

p 1    q 1
 /        \
2          2
Input: p = [1,2], q = [1,null,2]
Output: false

p 1    q 1
 / \    / \
2   1  1   2
Input: p = [1,2,1], q = [1,1,2]
Output: false

限制

• The number of nodes in both trees is in the range [0, 100].
• -10^4 <= Node.val <= 10^4

解題

這題最直觀的思路就是同時走訪一遍這兩棵樹，如果走到每個節點數值都相同，則這就是兩棵一樣的樹，反之則否。

需要注意的點：Space Complexity

Solution 1 - Recursion

用遞迴去判斷兩個現在的兩個節點是否相同，是的話就比較兩個子節點。既然是用遞迴就要寫出 Base case，此解法的 Base case 就是比較的節點是 null 的情況，兩者都 null 代表相同，這沒問題；但一個為 null 一個不是，就代表不相同了，可以直接回傳 false。

稍微要考慮的是一些 Corner case，例如有可能兩棵樹都是空的，而這也包含在 Base case 的檢查中，所以沒問題。

我的 JavaScript 解答如下

var isSameTree = function (p, q) {
  // Base case, p and q are null
  if (!p && !q) return true;
  if (!p || !q) return false;

  // Both p and q are not null
  if (p.val !== q.val) return false;
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

分析複雜度：

這題的 Time complexity 沒問題，就是兩棵樹的節點數，如果樹不一樣，就挑節點數小的（因為跑完某棵樹就結束了）。假設 p 及 q 的節點數是 m 和 n，Time complxity = O(min(n, m))，簡化一些令兩棵樹大小差不多，就是 O(n)

Space complexity 比較 tricky 一些，由於是呼叫 Recursion，本質上會產生一個 Call Stack。所以額外的空間就要看 Call Stack 最大的情況有多大了！

在走訪到 Leaf 時會觸底反彈，也就是到 Leaf 跑完後才會 Pop 掉 Call Stack 裡的 Function，所以看這棵樹的深度多深，Space Complexity 就是多少。最好的情況是一棵 Balanced Binary Tree，那深度就是 logn（若有 n 個節點），反之最差情況是像 Linked list 這樣（Fully skewed tree），深度就會是 n。

Solution 2 - Iteration

用 BFS (Breadth first search) 的思路來做，同樣是走訪整棵樹，但走的方式是廣度優先。實做的話就需要用到 Queue，把要走的節點丟入 Queue 裡面，再逐步展開。

我的 JavaScript 解答如下

var isSameTree = function (p, q) {
  const pQueue = [p];
  const qQueue = [q];

  // As long as queue is not empty
  while (pQueue.length && qQueue.length) {
    const cP = pQueue.shift();
    const cQ = qQueue.shift();

    // Base case, p and q are null
    if (!cP && !cQ) continue;
    if (!cP || !cQ) return false;

    // Both p and q are not null
    if (cP.val !== cQ.val) return false;

    pQueue.push(cP.left);
    qQueue.push(cQ.left);
    pQueue.push(cP.right);
    qQueue.push(cQ.right);
  }

  return true;
};

Time complexity 一樣是 O(n)。

Space Complexity 就變成要分析 Queue 的最大長度是多少了，我們看看下面這棵樹，

     1
   /   \
  2     3
 / \   / \
4   5 6   7

其走訪的方式，Queue 的變化為

[1]        -> Dequeue 1, add 2, 3
[2,3]      -> Dequeue 2, add 4, 5
[3,4,5]    -> Dequeue 3, add 6, 7
[4,5,6,7]  ->

也就是說，Queue 最長的情況會是 Leaf 的個數（Balanced binary tree），那就差不多是 n/2（如 7 節點，leaf 有 4；15 節點，leaf 有 7），那麼 Space complexity 就是 O(n)。

但最好情況就是 Fully skewed tree，像是 Linked list 這樣，那麼 Space complexity 就是 O(1)，每次 Add 後馬上就 Dequeue。

總結

這題是 LeetCode Easy 題，但要注意 Space complexity 的分析！

心得

第一次解題時間：2021-11-27

類似這種 Tree Traverse 的題目都要想想有沒有 Iterative 的解法，以這題來講，其實除了 BFS，也可以用 Stack 模擬 Recursion 的 DFS，就會是一樣的邏輯解此題了。