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