101. 对称二叉树

题目链接

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/symmetric-tree/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目描述

题目分析

1. 递归法

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr) return true; 
        return compare(root->left, root->right);
    }
    bool compare(TreeNode* left, TreeNode* right){//判断left 和right是否相等
        if(left == nullptr && right == nullptr) return true;
        if(left != nullptr && right != nullptr){
            if(left->val == right->val){
                //左右节点都不为空，且数值相同的情况:做下一层的判断
                bool outside = compare(left->left, right->right);
                bool insise = compare(left->right, right->left);
                return outside && insise;
            }else{
                return false;
            }
        }else{
            return false;
        }

    }
};

2. 迭代法
   队列-主要是判断对称结点的里侧和外侧是否相等。
   成对成对的比较

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        //8
        queue<TreeNode*> que;
        if(root == nullptr) return true;
        que.push(root->left);
        que.push(root->right);
        while(!que.empty()){
            TreeNode*leftNode = que.front();que.pop();
            TreeNode*rightNode = que.front();que.pop();
            if(leftNode != nullptr && rightNode != nullptr){
                if(leftNode->val == rightNode->val){
                    que.push(leftNode->left);
                    que.push(rightNode->right);
                    que.push(leftNode->right);
                    que.push(rightNode->left);
                }else{
                    return false;
                }
            }else if(leftNode == nullptr && rightNode != nullptr || leftNode != nullptr && rightNode == nullptr){
                return false;
            }
        }
        return true;
    }
};

栈
只要把queue改成statck