No. 100 - Same Tree

---

LeetCode 100 – Same 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.

Example 1.

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

Example 2.

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

---

解法

本題目的是要比對兩棵給定的 trees 的所有對應位置的 nodes 都相同。

這題其實就是 binary tree traversal 的應用問題，不論用 preorder, inorder, 或 postorder traversal 都可以得到解答，在這邊我們就只講解 postorder traversal 的解法。

使用 postorder traversal 解法的程式碼如下所示:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) // 兩棵 trees 都 traverse 到底沒有遇到不同的 nodes
      return true;
    if (!p || !q) // 有一棵 tree 先走到底
      return false;
    // postorder traversal
    if (!isSameTree(p->left, q->left)) // 先走訪兩棵 trees 的左 subtrees
      return false;
    if (!isSameTree(p->right, q->right)) // 再走訪它們的右 subtrees
      return false;
    return p->val == q->val; // 最後比較父 node 是否相同
  }
};

Postorder traversal 的作法從第 20 行開始，我們會同時走訪兩棵 trees 的左 subtree，只是走訪的函示是用 isSameTree，接著走訪右 subtree，最後在比對父 nodes 是否相同。

每次走訪左右 subtrees 都會回傳其是否為相同的 subtree。主要判斷 nodes 是否相同的部分有三處，首先是判斷兩棵 trees 走訪到最後是不是同時都走訪到底了，也就是第 15 行的判斷，這代表兩棵 trees 到目前走訪的 nodes 都相同。接著第 17 行會判斷是否有一棵 tree 先走訪完了但另一棵還沒，這種情況代表兩棵 trees 就不同了，最後就是第 24 行 postorder 最後走訪父 node 時的比對其是否相同，因為左右 subtrees 在前面走訪時就已經比完了。

複雜度分析

時間複雜度上，要比對兩棵 tree 是否相同就勢必走訪其所有 nodes 進行比對，所以複雜度為

$O(N)$。

空間複雜度上，因為是 recursive 的解法，需要存函式的 stack，其複雜度為

$O(H)$，

$H$ 為 tree 高。