[LintCode] Identical Binary Tree 동일 두 갈래 트리

Check if two binary trees are identical. Identical means the two binary trees have the same structure and every identical position has the same value.
Have you met this question in a real interview?
 
 
Example

    1             1
   / \           / \
  2   2   and   2   2
 /             /
4             4

are identical.

    1             1
   / \           / \
  2   3   and   2   3
 /               \
4                 4

are not identical.
 
LeetCode의 원제는 저의 이전 블로그 Same Tree를 참조하십시오.
 
해법 1:

class Solution {
public:
    /**
     * @aaram a, b, the root of binary trees.
     * @return true if they are identical, or false.
     */
    bool isIdentical(TreeNode* a, TreeNode* b) {
        if (!a && !b) return true;
        if (!a || !b) return false;
        return a->val == b->val && isIdentical(a->left, b->left) && isIdentical(a->right, b->right);
    }
};

 
해법 2:

class Solution {
public:
    /**
     * @aaram a, b, the root of binary trees.
     * @return true if they are identical, or false.
     */
    bool isIdentical(TreeNode* a, TreeNode* b) {
        stack<TreeNode*> s1, s2;
        if (a) s1.push(a); 
        if (b) s2.push(b);
        while (!s1.empty() && !s2.empty()) {
            TreeNode *t1 = s1.top(); s1.pop();
            TreeNode *t2 = s2.top(); s2.pop();
            if (t1->val != t2->val) return false;
            if (t1->left) s1.push(t1->left);
            if (t2->left) s2.push(t2->left);
            if (s1.size() != s2.size()) return false;
            if (t1->right) s1.push(t1->right);
            if (t2->right) s2.push(t2->right);
            if (s1.size() != s2.size()) return false;
        }
        return s1.empty() && s2.empty();
    }
};