### leetcode Question 109: Symmetric Tree

Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
    1
/ \
2   2
/ \ / \
3  4 4  3

But the following is not:
    1
/ \
2   2
\   \
3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

### Updated Solution (2014.02)

Analysis:
Use two queue to store each level of nodes back and force instead of storing the level.
Use a special node to store the empty node. (-999 in the code below).
Details see the comments in the code below.

### Code:

/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool valid(vector<int> &l){
int i=0;
int j=l.size()-1;
while (i<j){
if (l[i++]!=l[j--]){return false;}
}
return true;
}

bool isSymmetric(TreeNode *root) {
vector<int> l;  //store the values in current level

//q1 and q2 stores the current and next level TreeNodes
queue<TreeNode*> q1;
queue<TreeNode*> q2;

if (!root){return true;}

q1.push(root);
while ((!q1.empty()) || (!q2.empty())){  // exit only when both queue are empty
if (q2.empty()){   // current level is q1
while (!q1.empty()){ // push all the q1 nodes' childeren into q2
TreeNode* tmp = q1.front();
q1.pop();
l.push_back(tmp->val);
if (tmp->val!=-999){ // if current node is not a empty node
if (tmp->left!=NULL){q2.push(tmp->left);}
else{TreeNode* emp = new TreeNode(-999); q2.push(emp);} // store the empty node for the balance checking
if (tmp->right!=NULL){q2.push(tmp->right);}
else{TreeNode* emp = new TreeNode(-999); q2.push(emp);}
}
}

if (valid(l)==false){return false;}else // all the nodes in current level are stored, check if it is balanced
{l.clear();}

}else{  //current level is q2
while (!q2.empty()){  // push all the q2 nodes' childeren into q1
TreeNode* tmp = q2.front();
q2.pop();
l.push_back(tmp->val);
if (tmp->val!=-999){
if (tmp->left!=NULL){q1.push(tmp->left);}
else{TreeNode* emp = new TreeNode(-999); q1.push(emp);}
if (tmp->right!=NULL){q1.push(tmp->right);}
else{TreeNode* emp = new TreeNode(-999); q1.push(emp);}
}
}

if (valid(l)==false){return false;}else
{l.clear();}
}
}

return true;
}
};

### Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
# @param root, a tree node
# @return a boolean
def valid(self, l):
if cmp(l, l[::-1]) == 0:
return True
else:
return False
def isSymmetric(self, root):
if root == None:
return True
q1 = []
q2 = []
l = []
q1.append(root)
while len(q1) != 0 or len(q2) != 0:
if len(q1) == 0:
while len(q2) != 0:
node = q2.pop(0)
l.append(node.val)
if node.val != -999:
if node.left != None:
q1.append(node.left)
else:
q1.append(TreeNode(-999))
if node.right != None:
q1.append(node.right)
else:
q1.append(TreeNode(-999))
if self.valid(l) == False :
return False
else:
l = []
else:
while len(q1) != 0:
node = q1.pop(0)
l.append(node.val)
if node.val != -999:
if node.left != None:
q2.append(node.left)
else:
q2.append(TreeNode(-999))
if node.right != None:
q2.append(node.right)
else:
q2.append(TreeNode(-999))
if self.valid(l) == False :
return False
else:
l = []
return True



Updated Solution(2013.09)

Analysis:
BFS is a good way solving this problem, since BFS can get the nodes in every level.
But be careful with the empty nodes in this problem, if they are not well treated, it will effect the result.
Idea here is to save the empty nodes, with a special value (e.g. -999 in my code), and when we get all the nodes in one level, just need to do the testing (like palindrome).

Note that, the node with no children also need save its two "empty" children. If not, consider this example:
2
3            3
4    5      5    4
8  9        9  8
The last level, if you do not store the empty children from 4 and 5 in previous level, it becomes:
[8,9,9,8], which seems a true answer. But,  this level here is [#, #, 8, 9, #, #, 9, 8],  #!=8, which is a false answer!

Details see the code below:

Code:
/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool valid(vector<int> a){
int st=0;
int ed=a.size()-1;
while (st<ed){
if (a[st]!=a[ed]){return false;}
else{ st++; ed--;}
}
return true;
}

bool isSymmetric(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
queue<TreeNode* > q1;
queue<int> q2;
if (!root){return true;}
q1.push(root);
q2.push(0);
int l=0;
vector<int> r;
while (!q1.empty()){
if (l==q2.front()){
r.push_back(q1.front()->val);
}else{
if (valid(r)==false){return false;}
r.clear();
r.push_back(q1.front()->val);
l=q2.front();
}

if (q1.front()->val==-999){
q1.pop();
q2.pop();
continue;
}

if (q1.front()->left){
q1.push(q1.front()->left);
q2.push(l+1);
}else{
TreeNode* tmp = new TreeNode(-999);
q1.push(tmp);
q2.push(l+1);
}

if (q1.front()->right){
q1.push(q1.front()->right);
q2.push(l+1);
}else{
TreeNode* tmp = new TreeNode(-999);
q1.push(tmp);
q2.push(l+1);
}
q1.pop();
q2.pop();
}
if (!valid(r)){return false;}
return true;
}
};

1. class Solution {
public:
bool compare(TreeNode * left, TreeNode * right) {
if (left == NULL && right== NULL) return true;
if((left == NULL && right!= NULL) || (left != NULL && right == NULL) ) return false;
if (left->val != right->val) return false;
return (compare(left->left, right->right) && compare(left->right, right->left));
}
bool isSymmetric(TreeNode *root) {
if(root == NULL) return true;
return compare(root->left, root->right);

}
};

1. I made this way too. The queue method is complex for this question. Basic recursion is easier to do than using queues to store values at each level.

2. Thank you for sharing your article. Great efforts put it to find the list of articles which is very useful to know, Definitely will share the same to other forums.

kajal hot