# 101 - Symmetric Tree

解法一 - Recursion

要知道一棵樹是不是 symmetric，主要要判斷三件事：

1. 左右子樹的 root 是否一樣

2. 左子樹的左子樹 是否等於 右子樹的右子樹

3. 左子樹的右子樹 是否等於 右子樹的左子樹

然後 base case 就是走到 null 的時候。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return isEqual(root, root);
    }

private:
    bool isEqual(TreeNode* left, TreeNode* right) {
        if(left == NULL && right == NULL) return true;
        else if(left == NULL || right == NULL) return false;
        else return (left->val == right->val) 
                 && isEqual(left->left, right->right)
                 && isEqual(left->right, right->left);

    }
};

解法二 - Iteration

除了用 recursion 之外，我們也可以用來解，做法就是我們每次都把相對應要比較的兩個 node 放進 queue 裡面，每次 pop 出兩個 node 來比較。

實作如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        q.push(root);

        while(!q.empty()) {
            TreeNode* t1 = q.front();
            q.pop();
            TreeNode* t2 = q.front();
            q.pop();

            if(t1==NULL && t2==NULL) continue;
            if(t1==NULL || t2==NULL) return false;
            if(t1->val != t2->val)   return false;

            q.push(t1->left);
            q.push(t2->right);
            q.push(t1->right);
            q.push(t2->left);
        }

        return true;
    }
};