【二叉树算法题记录】101. 对称二叉树

题目描述

题目链接
给你一个二叉树的根节点 root，检查它是否轴对称。

题目分析

轴对称可以看作是每一层结点头尾对称（相等）。那么层序遍历就直接上了：

/**
 * 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) {
        // 对称实际上可以演变成每一层头尾对应的结点value是一样的
        // 可以用层序遍历
        queue<TreeNode*> q;
        //vector<vecotr<int>> all;
        if(root!=NULL) q.push(root);
        while(!q.empty()) {
            int size = q.size();
            vector<int> vec;
            while(size--) { // 遍历每层，然后记录他们的value到vec数组
                TreeNode* node = q.front(); q.pop();
                if(node) vec.push_back(node->val);
                else vec.push_back(404); // 如果结点不存在，就记录他的值为404

                if(node) {
                    q.push(node->left);
                    q.push(node->right);
                }
            }

            // 对vec数组进行判断
            for(int i = 0, j = vec.size()-1; i < j; i++, j--) {
                cout<< vec[i] << " " << vec[j] << endl;
                if(vec[i]!=vec[j]) return false;
            }
        }
        return true;
    }
};