題目網址：https://leetcode.cn/problems/same-tree/

題意：給兩 BT, 求兩者是否相等。

Solution 1：

想法：利用 DFS

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // 至少其中一個為 null, 兩個都為 null 時, return true; 其他情況皆為 false
        if (!(p && q)) {
            return p == q;
        }

        // 兩個皆不為 null
        return (p->val == q->val) &&
               isSameTree(p->left, q->left) &&
               isSameTree(p->right, q->right);
    }
};
  • time：$O(min(m, n))$ ➔ 其中 m、n 分別是兩個 BT 的 node 個數, 被訪問到的 node 個數不超過較小的 BT 之節點個數
  • space：$O(min(m, n))$ ➔ 遞迴深度不超過較小的 BT 之節點個數

Solution 2：

想法：利用 BFS, 要注意 nullptr 也要 insert 到 queue 中, 否則下方範例會出錯

e.g. 左邊 = [1, null, 2], 右邊 = [1, 2]

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // 至少其中一個為 null, 兩個都為 null 時, return true; 其他情況皆為 false
        if (!(p && q)) {
            return p == q;
        }

        // 兩個皆不為 null
        queue<TreeNode*> q1;
        queue<TreeNode*> q2;
        q1.emplace(p);
        q2.emplace(q);

        while (!q1.empty() && !q2.empty()) {
            const int n1 = q1.size(), n2 = q2.size();

            if (n1 != n2) {
                return false;
            }

            for (int i = 0; i < n1; ++i) {
                const auto cur1 = q1.front();
                q1.pop();

                const auto cur2 = q2.front();
                q2.pop();

                // 這邊做判斷是為了避免下面出錯
                if (!(cur1 && cur2)) { // 其中一個為 null
                    if (cur1 != cur2) { // 一個是 null, 一個不是
                        return false;
                    } else { // 兩個皆為 null
                        continue;
                    }
                }

                if (cur1->val != cur2->val) {
                    return false;
                }

                addChild(q1, cur1);
                addChild(q2, cur2);
            }
        }
        return q1.empty() && q2.empty();
    }

private:
    // nullptr 也要 insert 到 queue 中
    void addChild(queue<TreeNode*>& q, TreeNode* node){
        q.emplace(node->left);
        q.emplace(node->right);
    }
};
  • time：$O(min(m, n))$ ➔ 其中 m、n 分別是兩個 BT 的 node 個數, 被訪問到的 node 個數不超過較小的 BT 之節點個數
  • space：$O(min(m, n))$ ➔ q 的元素個數不超過較小的 BT 之節點個數