###### tags: `Leetcode` `easy` `tree` `python` `c++` `Top 100 Liked Questions`

# 101. Symmetric Tree

## [題目來源:] https://leetcode.com/problems/symmetric-tree/

## 題目:
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

**Follow up: Could you solve it both recursively and iteratively?**

## 解題思路:
Recursive: 同P100 Same Tree邏輯，只是要注意是對稱的!!
Iterative: 兩個queue分別存root的左子與右子 pop逐一比較

## Python (Recursive & Iterative):

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

#法1: recursive
'''
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            #root空時 為false 所以負負得正 才能進入這判斷式
            return True
        else:
            return self.mirror(root.left,root.right)
        
    def mirror(self,left,right):
        if left==None and right==None:
            return True
        if left and right and left.val==right.val:
            return self.mirror(left.left,right.right) and self.mirror(left.right,right.left)
        else:
            return False
'''
#iterative
class Solution:
    def isSymmetric(self, root):
        if not root:
            return True
        stackLeft = [root.left]
        stackRight = [root.right]
        while stackLeft and stackRight:
            left = stackLeft.pop()
            right = stackRight.pop()
            if  (left==None) and (right==None):
                #注意!!!!!!!!!!!是continue
                continue
            elif not left or not right:
                #左右一邊空
                return False
            if left.val != right.val:
                return False
            stackLeft.append(left.left)
            stackLeft.append(left.right)
            stackRight.append(right.right)
            stackRight.append(right.left)
        return True
if __name__ == '__main__':
    root=TreeNode(1)
    root.insertLeft(2)
    root.insertRight(2)
    root.left.insertLeft(3)
    root.left.insertRight(4)
    root.right.insertLeft(4)
    root.right.insertRight(3)
    root.printTree()

    result = Solution()
    ans = result.isSymmetric(root)
    print(ans)
    

## C++ (Recursive & Iterative):

#include<iostream>
#include<queue>
#include<vector>
#include<stack>
using namespace std;

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

void insertLeft(TreeNode *root, int data){
    TreeNode *tmp = root;
    while( tmp->left != nullptr){
        tmp=tmp->left;
    }
    TreeNode *new_Left = new TreeNode(data);
    tmp->left=new_Left;
}

void insertRight(TreeNode *root, int data){
    TreeNode *tmp=root;
    while (tmp->right != nullptr){
        tmp=tmp->right;
    }
    TreeNode *new_Right= new TreeNode(data);
    tmp->right=new_Right;
}

void printTree(TreeNode *root){
    TreeNode *tmp=root;
    queue<TreeNode *> que;
    que.push(tmp);
    vector<int> res;
    while ( !que.empty() ){
        TreeNode *cur_root=que.front();
        que.pop();
        res.push_back(cur_root->val);
        if (cur_root->left!=nullptr)
            que.push(cur_root->left);
        if (cur_root->right!=nullptr)
            que.push(cur_root->right);
    }
    for (int i=0; i<res.size(); i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
}

class SolutionRe{
public:
    bool isSymmetric(TreeNode* root){
        if(!root)
            return true;
        return mirror(root->left,root->right);
    }
    bool mirror(TreeNode* p, TreeNode* q){
        if (!p && !q)
            return true;
        if (!p || !q)
            return false;
        if (p->val == q->val)
            return mirror(p->left,q->right) && mirror(p->right,q->left);
        return false;
    }
};

class SolutionIt {
public:
    bool isSymmetric(TreeNode* root) {
        //iterative
        if (!root)
            return true;
        queue<TreeNode*> queL;
        queue<TreeNode*> queR;
        queL.push(root->left);
        queR.push(root->right);
        while (!queL.empty() && !queR.empty()){
            TreeNode *rootL=queL.front(); queL.pop();
            TreeNode *rootR=queR.front(); queR.pop();
            if (rootL==nullptr && rootR==nullptr)
                continue;
            if ( !rootL || !rootR)
                return false;
            if (rootL->val != rootR->val)
                return false;
            else{
                queL.push(rootL->left);
                queL.push(rootL->right);
                queR.push(rootR->right);
                queR.push(rootR->left);
            }
        }
        return true;
    }
};

int main(){
    TreeNode *root= new TreeNode(1);
    insertLeft(root,2);
    insertRight(root,2);
    insertLeft(root->left,3);
    insertRight(root->left,4);
    insertLeft(root->right,4);
    insertRight(root->right,3);
    printTree(root);

    SolutionRe res;
    bool ans=res.isSymmetric(root);
    cout<<ans<<endl;

    SolutionIt res2;
    bool ans2=res2.isSymmetric(root);
    cout<<ans2<<endl;

    return 0;
}