101. 对称二叉树（递归与迭代方法）

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false
 

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

使用迭代可以达到100%的效率，尽量多用迭代

/**
 * 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) {
//         return compare(root->left, root->right);
//     }

//     bool compare(TreeNode* left, TreeNode* right){
//         if(left == nullptr && right == nullptr){
//             return true;
//         }else if (left != nullptr && right == nullptr){
//             return false;
//         }else if (left == nullptr && right != nullptr){
//             return false;
//         }else if (left->val != right->val){
//             return false;
//         }

//         bool outside = compare(left->left, right->right);
//         bool inside = compare(left->right, right->left);
//         bool isSame = outside && inside;
//         return isSame;
//     }
// };

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL)
            return true;
        //使用两个队列进行操作
        queue<TreeNode*> left;
        queue<TreeNode*> right;
        left.push(root->left);
        right.push(root->right);
        while(!left.empty() && !right.empty()){
            TreeNode* left_node = left.front();
            TreeNode* right_node = right.front();
            left.pop();
            right.pop();
            if (left_node == NULL && right_node == NULL)
                continue;
            if ((left_node == NULL && right_node != NULL) || (left_node != NULL && right_node == NULL))
                return false;
            if (left_node->val != right_node->val)
                return false;
            // 注意进对顺序
            left.push(left_node->left);
            left.push(left_node->right);
            right.push(right_node->right);
            right.push(right_node->left);
        }
        return true;
    }
};
static int x=[](){
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    return 0;
}();