100. Same Tree

題目 / Problem

中文： 給定兩棵二元樹的根節點 p 和 q，請判斷這兩棵樹是否「相同」。兩棵二元樹被視為相同，需要同時滿足：結構完全一致（每個位置有節點或沒節點都要對應），且對應位置的節點值也相同。

English: Given the roots of two binary trees p and q, determine whether they are the same. Two binary trees are the same when they are structurally identical (every position that has a node in one tree must have a node in the other, and vice versa) and the values at every corresponding position are equal.

Constraints / 限制： - 兩棵樹的節點數都在 [0, 100] 範圍內 / Both trees have between 0 and 100 nodes. - -10^4 <= Node.val <= 10^4

Worked example / 範例： - Input: p = [1,2,3], q = [1,2,3] → Output: true（結構和值都一樣 / same shape, same values） - Input: p = [1,2], q = [1,null,2] → Output: false（一個把 2 放在左邊，一個放在右邊，結構不同 / the 2 is a left child in one tree and a right child in the other）

名詞解釋 / Glossary

• 二元樹 / binary tree：一種樹狀資料結構，每個節點最多有兩個子節點，分別叫「左子節點」和「右子節點」。/ A tree structure where each node has at most two children, called the left child and the right child.
• 節點 / node：樹裡的一個元素，通常包含一個值 val，以及指向左、右子節點的兩個指標 left、right。/ One element of the tree, holding a value val and two pointers left and right to its children.
• 根節點 / root：整棵樹最上面、沒有父節點的那個節點；p 和 q 就是兩棵樹的根。/ The topmost node with no parent; p and q are the roots of the two trees.
• 空節點 / NULL node：某個子節點不存在時，指標會是 NULL（C）或 nullptr（C++）。在陣列表示法中寫成 null。/ When a child does not exist, the pointer is NULL/nullptr; shown as null in the array form.
• 遞迴 / recursion：函式呼叫自己來解決規模更小的子問題。這裡用「比較根節點 → 再比較左子樹 → 再比較右子樹」的方式層層拆解。/ A function calling itself on smaller subproblems; here we compare the roots, then recurse into the left subtrees, then the right subtrees.
• 深度優先搜尋 / DFS (Depth-First Search)：一種遍歷策略，沿著一條路徑盡量往下走到底，再回頭走其他分支。遞迴天然就是 DFS。/ A traversal that goes as deep as possible along one branch before backtracking; recursion naturally implements it.
• 指標解參考 / pointer dereference：用 p->val 讀取指標 p 指向的節點裡的 val 欄位；-> 是「先解參考再取欄位」的簡寫。/ p->val reads the val field of the node that pointer p points at; -> means "dereference then access field."

思路

最直覺的想法可能是：把兩棵樹分別走一遍、記錄下來，再比較兩份紀錄是否一模一樣。但這樣需要額外儲存整棵樹的資訊，而且要小心把「空節點」也記錄進去（否則 [1,2] 和 [1,null,2] 這種只差在左右位置的情況會被誤判為相同）。其實我們不需要先存再比，可以「邊走邊比」。關鍵觀察是：兩棵樹相同，等價於「根節點相同」而且「左子樹彼此相同」而且「右子樹彼此相同」——這是一個可以遞迴的定義。於是我們寫一個函式同時比較 p 和 q：先處理最單純的邊界情況，如果兩個都是空節點，代表這條路走到底且一致，回傳 true；如果只有一個是空、另一個不是，結構就對不上，回傳 false；如果兩個都非空但值不同，也回傳 false。過了這三關，代表當前這個節點本身一致，接著就遞迴去問「左邊一不一樣」和「右邊一不一樣」，兩者都成立整體才算相同。這個做法會走訪每個節點恰好一次，非常高效，而且不需要額外的資料結構，只用到遞迴呼叫本身的堆疊空間。

The brute-force instinct might be to serialize both trees into some record and then compare the records. That works but costs extra storage, and you must be careful to encode the null gaps too — otherwise [1,2] and [1,null,2], which differ only in whether the 2 hangs on the left or the right, would look identical. We can avoid the extra storage by comparing as we walk. The key insight is a recursive definition: two trees are the same exactly when their roots match and their left subtrees are the same and their right subtrees are the same. So we write one function that compares p and q together. First handle the simplest base cases: if both are NULL, this branch bottomed out in agreement → true; if exactly one is NULL, the shapes disagree → false; if both exist but their values differ → false. If we survive those checks, the current nodes agree, so we recurse to ask "is the left side the same?" and "is the right side the same?", requiring both to hold. This visits every node exactly once, uses no auxiliary data structure, and only spends the call-stack space inherent to the recursion.

逐步走查 / Walkthrough

Example: p = [1,2,3], q = [1,2,3]. Both trees look like root 1 with left child 2 and right child 3.

We call isSameTree(p, q). Each row is one call; indentation shows recursion depth.

每個節點都被比較到，且沒有任何一步回傳 false，最終結果為 true。/ Every node got compared, no step returned false, so the final answer is true.

Solution — C

// 演算法：遞迴地同時比較兩棵樹。相同 = 根相同 + 左子樹相同 + 右子樹相同。
// Algorithm: recursively compare both trees at once. Same = roots equal
// + left subtrees same + right subtrees same. Visit each node once (DFS).

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    // 邊界1：兩個都是空節點，這條路走到底且一致 / Base 1: both NULL — matched all the way down
    if (p == NULL && q == NULL) return true;

    // 邊界2：只有一個是空，結構對不上 / Base 2: exactly one is NULL — shapes differ
    // （若上面沒回傳，代表不會兩個都為 NULL；這裡任一為 NULL 就是「只有一個」）
    // (if we got past base 1, at most one is NULL; either being NULL means mismatch)
    if (p == NULL || q == NULL) return false;

    // 邊界3：兩個都非空，但值不同 / Base 3: both exist but values differ
    // p->val 是「解參考指標 p 取得節點的 val 欄位」/ p->val dereferences p and reads its val field
    if (p->val != q->val) return false;

    // 當前節點一致，遞迴檢查左子樹與右子樹，兩者都要成立 (&& 短路)
    // Current node matches; recurse on left and right — both must hold (&& short-circuits)
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

Solution — C++

// 演算法：與 C 版相同，遞迴同時比較兩棵樹。
// Algorithm: same as the C version — recursively compare both trees together (DFS).
// Same = roots equal AND left subtrees same AND right subtrees same.

/**
 * 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) {
        // 邊界1：兩個都是空節點 → 相同 / Base 1: both null → same (nullptr 是 C++ 的空指標字面值)
        if (!p && !q) return true;   // !p 為真代表 p 是 nullptr / !p is true when p is nullptr

        // 邊界2：只有一個是空 → 結構不同 / Base 2: exactly one is null → different shape
        if (!p || !q) return false;

        // 邊界3：兩個都非空但值不同 → 不同 / Base 3: both exist but values differ → not same
        if (p->val != q->val) return false;

        // 遞迴比較左、右子樹，兩者皆真才回傳真 / Recurse on both subtrees; both must be true
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

複雜度 / Complexity

• Time: O(n) — 其中 n 是較小那棵樹的節點數（一旦某側先變成 NULL，比較就會停在那裡）。每個節點最多被造訪並比較一次，沒有重複工作，所以時間與節點數成正比。/ where n is the number of nodes in the smaller tree (once one side hits NULL the comparison stops there). Each node is visited and compared at most once, so time is linear in the node count.
• Space: O(h) — h 是樹的高度，來自遞迴呼叫的堆疊深度。最壞情況樹退化成一條鏈時 h = n，變成 O(n)；平衡樹則約為 O(log n)。除了堆疊外沒有用到額外空間。/ where h is the tree height — this is the recursion call-stack depth. Worst case (a tree that degenerates into a chain) h = n → O(n); a balanced tree is about O(log n). No extra data structures are used.

Pitfalls & Edge Cases

• 空節點的順序很重要 / NULL checks must come first：一定要在讀取 p->val 之前先檢查 p、q 是否為空。若 p 是 NULL 卻寫 p->val，就是對空指標解參考，會直接崩潰。程式碼把三個邊界檢查排在遞迴之前正是為了避免這點。/ Always test for NULL before touching p->val. Dereferencing a null pointer crashes; the three base-case guards run before any ->val access precisely to prevent this.
• 結構 vs. 值兩者都要比 / structure AND value both matter：[1,2] 和 [1,null,2] 的節點值集合看起來一樣，但左右位置不同。「只有一個為空回傳 false」這關就是用來抓這種結構差異的。/ [1,2] vs [1,null,2] share the same value set but differ in shape; the "exactly one is NULL → false" branch is what catches this.
• 兩棵都是空樹 / both trees empty：p 和 q 都是 NULL（即 [] 與 []）應回傳 true，由邊界1處理。/ Two empty trees should return true, handled by base case 1.
• 不要漏掉 && 的兩側 / don't forget both subtrees：只比左子樹或只比右子樹都會漏判。必須左、右都相同整體才相同；&& 也會在左側為 false 時短路、省去不必要的右側遞迴。/ Comparing only one subtree misses differences; both left and right must match. && also short-circuits — if the left side is false it skips the right recursion.
• 不需要擔心數值溢位 / no overflow concern：值域是 [-10^4, 10^4]，遠在 int 範圍內，直接用 != 比較即可。/ Values fit comfortably in int, so a plain != comparison is safe.