[数据结构与算法]【LeetCode-101 | 对称二叉树】

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;


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:
    // 1.确定函数入参及返回值
    bool compare(TreeNode* left, TreeNode* right) {
        // 2.确定递归终止条件
        if(left == nullptr && right != nullptr) return false;
        else if(left != nullptr && right == nullptr) return false;
        else if(left == nullptr && right == nullptr) return true;
        else if(left->val != right->val) return false;

        // 3.确定单层递归逻辑
        /* 外侧 */
        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 == nullptr) return true;
        return compare(root->left, root->right);
    }
};


/* 迭代法 */
class Solution {
public: 
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr) 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;
    }
};