题目描述

原题链接：101. 对称二叉树

解题思路

一、后序遍历

1、递归

设置两个指针进行遍历对比，分别指向互相对称位置：左子树的左孩子与右子树的右孩子互对称，左子树的右孩子与右子树的左孩子互对称。

每次遍历前先判定对称位置上是否有结点，是否值相同。
（1）当都为空时，说明遍历到底；
（2）当一个为空，另一个不为空时，说明互不对称；
（3）当双方值不相同时，说明互不对称。

然后，再分别让两个指针后续孩子的对称位置进行遍历：左的左与右的右，左的右与右的左。子树判定完，将结果返回给上一层。

/**
 * 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) {
        // 左右都为空时，说明遍历到底，返回true
        if(!left && !right)             return true;            
        // 一个为空，一个不为空，返回false
        if(!left || !right)             return false;
        // 对称结点不相等，返回false。注意：为了防止空指针异常，这里不能和第一行用||共写
        if(left->val != right->val)     return false;
        // 左结点的左孩子与右结点的右孩子为对称位置，此时遍历为左右中
        bool leftcom = compare(left->left, right->right);
        // 左结点的右孩子与右结点的左孩子为对称位置，此时遍历为右左中
        bool rightcom = compare(left->right, right->left);
        return leftcom & rightcom;		// 将结果返回给上一层结点
    }
    bool isSymmetric(TreeNode* root) {
        if(!root)       return false;
        return compare(root->left, root->right);
    }
};

2、非递归

每次从栈中弹出两个元素进行操作，这两个元素应分别为互对称位置元素。
然后判定是否为对称元素，不为对称元素则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 isSymmetric(TreeNode* root) {
        if(!root)       return false;
        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)         return false;
            if(leftnode->val != rightode->val)  return false;
            // 注意加入顺序，左的左与右的右互配，左的右与右的左互配，
            st.push(leftnode->left);
            st.push(rightnode->right);
            st.push(leftnode->right);
            st.push(righttnode->left);
        }
        return true;
    }
};

二、层次遍历

注意：此时若要用while(n--)的话，需要n -= 2。否则会报错

Line 26: Char 30: runtime error: member access within misaligned address 0xbebebebebebebebe for type ‘TreeNode’, which requires 8 byte alignment (solution.cpp)
0xbebebebebebebebe: note: pointer points here
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:35:30

因为不需要有关层次的信息，因此可以直接用最外层的while循环即可，不用再求出当前队列中的元素个数，再while(n--)

/**
 * 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) {
        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)             return false;                
            if(leftnode->val != rightnode->val)     return false;
            que.push(leftnode->left);
            que.push(rightnode->right);
            que.push(leftnode->right);
            que.push(rightnode->left);
        }
        return true;
    }
};

参考文章：101. 对称二叉树