sundeepblue
3/27/2014 - 4:00 AM

Symmetric Tree

Symmetric Tree

// ================================
// solution 1: recursive
bool isSymmetric(TreeNode *root) {
    if(!root) return true;
    if(!root->left && !root->right) return true;
    return is_sym(root->left, root->right);
}
bool is_sym(TreeNode *r1, TreeNode *r2) {
    if(!r1 && !r2) return true;
    if(!r1 && r2 || r1 && !r2) return false;
    if(r1->val != r2->val) return false;
    return is_sym(r1->left, r2->right) && is_sym(r1->right, r2->left);
}

// ================================
// solution 2: BFS
bool isSymmetric(TreeNode *root) {
    if(!root) return true;
    if(!root->left && !root->right) return true;
    deque<TreeNode*> q1, q2;
    q1.push_back(root);
    while(!q1.empty()) {
        while(!q1.empty()) {  // gist, note this while
            TreeNode *r = q1.front();
            q1.pop_front();
            if(!r) continue; // !!!
            q2.push_back(r->left); // even when note is NULL, push it
            q2.push_back(r->right);
        }
        // check if q2 is symmetric
        int N = q2.size();
        if(N%2 != 0) return false;
        //if(is_all_null(q2)) break;
        int i = 0, j = q2.size() - 1;
        while(i < j) {
            if(is_equal(q2[i], q2[j]) == false) return false;
            i++;
            j--;
        }
        q1 = q2;
        q2.clear();
    }
    return true;
}

bool is_equal(TreeNode *r1, TreeNode *r2) {
    if(!r1 && !r2) return true;
    if(!r1 && r2 || r1 && !r2) return false;
    if(r1->val != r2->val) return false;
    return true;
}
bool is_all_null(deque<TreeNode*> &q) {
    int N = q.size();
    if(N == 0) return true;
    int null_num = 0;
    for(int i=0; i<N; i++) 
        if(q[i] == NULL) null_num++;
    if(N == null_num) return true;
    return false;
}