###### tags: `leetcode`
# Question 101. Symmetric Tree
### Description:
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
### Solution:
Two solution:
- Recursive
- compare cur->left_subtree+cur->right_subtree
- BFS
- Breadth First Search
- top down
- Use Queue
### AC code
Code 1, Recursive

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //recursive
    bool isSymmetric(TreeNode* root) {
        if(root==NULL)
            return true;
        return test(root->left, root->right);
    }
    bool test(TreeNode* p, TreeNode* q){
        if(p==NULL && q==NULL)
            return true;
        if(p==NULL || q==NULL)
            return false;
        if(p->val!=q->val)
            return false;
        return test(p->left, q->right)&&test(p->right, q->left);
    }

code 2, BFS and vector

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root==NULL)
            return true;
        queue<TreeNode*> r;
        r.push(root);
        TreeNode* tmp;
        vector<int> sym;
        while(!r.empty()){
            int n = sym.size();
            //cout<<"n: "<<n<<endl;
            for(int i = 0 ; i < n/2 ; i++){
                cout<<sym[i]<<" "<<sym[i+(n/2)]<<endl;
                if(sym[i]!=sym[n-1-i])
                    return false;
            }
            sym.clear();
            
            n = r.size();
            for(int i = 0 ; i < n ; i++){
                tmp = r.front();
                r.pop();
                if(tmp->right!=NULL){
                    r.push(tmp->right);
                    sym.push_back(tmp->right->val);
                }
                else
                    sym.push_back(-1);
                if(tmp->left!=NULL){
                    r.push(tmp->left);                                    
                    sym.push_back(tmp->left->val);
                }
                else
                    sym.push_back(-1);

            }
        }
        return true;
    }
};