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;
}``````