100. Same Tree - cocoder39/coco39_LC GitHub Wiki

100. Same Tree

Solution 1: recursion. time complexity is O(n) where n is max(size_of_p, size_of_q), space complexity is O(h) where h is min(height_of_p, height_of_q)

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

Solution 2 (preferred): iteration with stack. time complexity is O(n) where n is max(size_of_p, size_of_q), space complexity is O(h) where h is min(height_of_p, height_of_q)

bool isSameTree(TreeNode* p, TreeNode* q) {
        stack<pair<TreeNode*, TreeNode*>> stk;
        stk.push(make_pair(p, q));
        while (! stk.empty()) {
            auto nodePair = stk.top();
            stk.pop();
            if (! nodePair.first && ! nodePair.second) {
                continue;
            } else if (! nodePair.first || ! nodePair.second || nodePair.first->val != nodePair.second->val) {
                return false;
            } else {
                stk.push(make_pair(nodePair.first->left, nodePair.second->left));
                stk.push(make_pair(nodePair.first->right, nodePair.second->right));
            }
        }
        return true;
    }