题解 | #牛群的轴对称结构#

考察知识点： 树的层序遍历、STL、宽度优先搜索

题目分析：

 判断树是否是对称结构，可以通过遍历每一层，判断每一层中的结点是否是回文串来解决。

 层序遍历时，一般需要使用队列，从头节点考试，将一层中节点的下一层节点放入队列中，直到队列为空时停止。

 为了判断树的结构是否是对称的，我们需要记录某个节点的位置（是左子树的根节点还是右子树的根节点），可以通过将nullptr记录成#，这样就保留了树中节点的结构。

 每次层序遍历时，首先获记录该层的节点数。因为每遍历到一个值，就需要将他的子树都加进来，这些节点都保存到队列中，通过记录的节点数可以明确哪些节点是属于某一层的。遍历完这一层后判断使用这一层的值所组成的字符串是否是回文串，是回文串则满足条件。

所用编程语言： C++

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    bool isSymmetric(TreeNode* root) {
        // write code here
        queue<TreeNode*> cows;
        cows.push(root);
        while (!cows.empty()) {
            int size = cows.size();
            string cs = "";
            for (int i = 0; i < size; i++) {
                TreeNode *p = cows.front();
                if (!p) {
                    cs += '#';
                    cows.pop();
                    continue;
                }
                cs += p->val;
                cows.pop();
                cows.push(p->left);
                cows.push(p->right);
            }
            int l = 0, r = size - 1;
            while (l < r) {
                if (cs[l] != cs[r]) return false;
                l++, r--;
            }
        }
        return true;
    }
};