[数据结构与算法]力扣算法二叉树篇:对称二叉树

递归：
递归三部曲：
1、确定递归函数的参数和返回值
要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以参数是左子树结点和右子树结点。返回值为bool类型
2、确定终止条件
结点为空的情况和不为空的情况

 if(left == NULL && right!=NULL){
            return false;
        }
        else if(left!=NULL && right==NULL){
            return false;
        }
        else if(left == NULL && right == NULL){
            return true;
        }else if(left->val != right->val){
            return false;
        }

3、确定单层递归逻辑
单层递归的逻辑就是处理左右结点均不为空，且数值相同的情况。
比较左节点的左孩子和右节点的右孩子，比较左节点的右孩子和右节点的左孩子，如果左右都对称就返回true。否则返回false

/**
 * 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 compare(TreeNode*left,TreeNode*right){
        //首先排除空结点的情况
        if(left == NULL && right!=NULL){
            return false;
        }
        else if(left!=NULL && right==NULL){
            return false;
        }
        else if(left == NULL && right == NULL){
            return true;
        }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;
    }
    bool isSymmetric(TreeNode* root) {
        //对称二叉树
        if(root ==NULL){
            return true;
        }
        return compare(root->left,root->right);
    }
};

迭代：队列实现

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        //判空
        if(root == NULL){
            return true;
        }
        //队列 实现迭代法
        queue<TreeNode*> que;
        //将左子树头结点加入队列
        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 && !rightNode){
                //对称
                continue;
            }
            //左右之中有一个结点不为空 或者都不为空但数值不相同
            if((!leftNode || !rightNode || (leftNode->val!=rightNode->val))){
                return false;
            }
            //为下一轮比较做准备
            //加入左节点左孩子和右节点右孩子
            que.push(leftNode->left);
            que.push(rightNode->right);
            //加入左节点右孩子和右节点左孩子
            que.push(leftNode->right);
            que.push(rightNode->left);
        }
        //出了循环
        return true;
    }
};

栈实现：把队列换成栈即可 两个结点两个结点取出来比较

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        //判空
        if(root == NULL){
            return true;
        }
        //栈 实现迭代法
        stack<TreeNode*> st;
        //将左子树头结点加入栈
        st.push(root->left);
        //将右子树头结点加入栈
        st.push(root->right);
        //判断这两个树是否相互翻转
        while(!st.empty()){
            TreeNode * leftNode = st.top();
            st.pop();
            TreeNode* rightNode = st.top();
            st.pop();
            //左节点为空、右节点为空
            if(!leftNode && !rightNode){
                //对称
                continue;
            }
            //左右之中有一个结点不为空 或者都不为空但数值不相同
            if((!leftNode || !rightNode || (leftNode->val!=rightNode->val))){
                return false;
            }
            //为下一轮比较做准备
            //加入左节点左孩子和右节点右孩子
            st.push(leftNode->left);
            st.push(rightNode->right);
            //加入左节点右孩子和右节点左孩子
            st.push(rightNode->left);
            st.push(leftNode->right);
           
        }
        //出了循环
        return true;
    }
};