题解 | #牛群的对称排列# 层序遍历

层序遍历给定的树，将每层的结果存入数组中，并判断数组是否对称

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  private:
    bool symmetric(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            if (nums[l] == nums[r]) {
                l++;
                r--;
            } else {
                return false;
            }
        }
        return true;
    }
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    bool isSymmetric(TreeNode* root) {
        if (!root) {
            return false;
        }
        queue<TreeNode*> qu;
        qu.push(root);
        while (!qu.empty()) {
            int size = qu.size();
            if (size % 2 != 0 && size > 1) {
                return false;
            }
            vector<int> temp;
            for (int i = 0; i < size; i++) {
                TreeNode* node = qu.front();
                qu.pop();
                temp.push_back(node->val);
                if (node->left) {
                    qu.push(node->left);
                }
                if (node->right) {
                    qu.push(node->right);
                }
            }
            if (!symmetric(temp)) {
                return false;
            }
        }
        return true;
    }
};

时间复杂度：O(n)，其中n是二叉树中节点的数量。这是因为代码通过BFS遍历了整个二叉树，每个节点都会被访问一次

空间复杂度：O(n)，主要是由队列qu和临时数组temp所占用的空间决定的。在最坏情况下，队列中会存储二叉树中所有节点，因此空间复杂度与节点数量成正比