力扣：101. 对称二叉树

力扣：101. 对称二叉树
代码随想录
题目：
给你一个二叉树的根节点 root ， 检查它是否轴对称。

思路：
①递归：遍历左右子树。左边左右中，右边右左中。假如两个容器相等则对称。
1：确定递归函数的参数和返回值：
2：确定终止条件：
即写出return的情况
3：确定单层递归：
有递归的情况,这也是一种情况也要返回值。 m
每种情况都要返回值。

这个递归函数的名字叫做：比较对应节点是否相等。
一层一层往下走，先把外面全部比较完然后比较里面，最后取交集看树是否对称。
左节点为空，右节点不为空，不对称，return false
左不为空，右为空，不对称 return false
左右都为空，对称，返回true
左右都不为空，比较节点数值，不相同就return false

左右都不为空，节点值相同，此时就不看节点了，此时就看树是否对称了，因为运用了递归就得整体来看了。

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

		bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
        bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
        bool isSame = outside && inside;                    // 左子树：中、 右子树：中 （逻辑处理）
        return isSame;
将上面的换成下面的也可以
else return compare(left->left, right->right) && compare(left->right, right->left);

②用队列：同时出两个节点同时比较，然后入四个节点，要对应入（左孩子左与右孩子又同时入…）

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        queue 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;
            }

            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            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 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(leftNode->right);
            st.push(rightNode->left);
        }
        return true;
    }
};