Identical Binary Tree

Description

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.

Example
    1             1
   / \           / \
  2   2   and   2   2
 /             /
4             4
are identical.
    1             1
   / \           / \
  2   3   and   2   3
 /               \
4                 4
are not identical.

Link

Lintcode_ladder

Method

1. BFS,
   we push every node into queue,
   comparing structure and value
2. x

Example

1. 1

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
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) {
        // Write your code here
        if (!a && !b) {
            return true;
        }
        queue<TreeNode*> q;
        q.push(a);
        q.push(b);
        while (q.size() > 1) {
            TreeNode* left = q.front();
            q.pop();
            TreeNode* right =q.front();
            q.pop();
            // when on the front, we check the validness of corresponding
            //  left and right
            // then the value
            // Once find no matching, return false
            if (!left && !right) {
                continue;
            } else if (left && right) {
                if (left->val != right->val) {
                    return false;
                }
            } else {
                return false;
            }
            // all child will be pushed into queue
            q.push(left->left);
            q.push(right->left);
            q.push(left->right);
            q.push(right->right);
        }
        return true;
    }
};

Similar problems

x

Tags

x