LeetCode 100. Same Tree [Easy] [C++] 解題筆記

給我們兩個 binary tree，要我們判斷兩者是不是一樣的。

EX:

        Input:    1          1

                      / \        / \
                   2   1     1   2

                 [1,2,1],   [1,1,2]

        Output: false

想法:

    這題很直覺，直接同時對兩個 tree 做 traverse，在過程中一旦發現某個 node 不一樣就可以直接返回 false了。

完整程式碼:

解法一(recursive):

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL && q == NULL) { return true; }
        if (p == NULL || q == NULL) { return false; }
        if (p->val != q->val) { return false; }
        return isSameTree(p->left, q->left) &&
               isSameTree(p->right, q->right);
    }   
};

解法二(iterative):

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<pair<TreeNode*, TreeNode*>> que;
        que.push(make_pair(p, q));
        bool same = true;
        while (!que.empty()) {
            auto current = que.front();
            que.pop();
            if (current.first == NULL && current.second == NULL) { continue; }
            if (current.first == NULL || current.second == NULL) {
                same = false;
                break;
            }
            if (current.first->val != current.second->val) {
                same = false;
                break;
            }
            else {
                que.push(make_pair(current.first->left, current.second->left));
                que.push(make_pair(current.first->right, current.second->right));
            }
        }
        return same;
    }
};