题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

思路上还是广度优先搜索（BFS）来做的。BFS是依托于STL的queue作为容器作为存储空间的，并且树的每一层节点的处理都放到一个内部的while循环中；

使用一个vector存储层内节点元素值，然后判断这个vector是否为对称的。如果对称，还要考虑元素个数，除了第一层之外都应该是偶数个元素。这样的话没有考虑到null节点的处理。

如果节点为null则存储一个0（假定样例节点值都是大于0的），这样就不用考虑vector元素个数的问题了。

代码如下：

class Solution {

public:

	bool isSymmetrical(TreeNode* pRoot)

	{

		if (pRoot == NULL){

			return true;

		}

		queue<TreeNode*> Q;

		Q.push(pRoot);

		bool first_layer = true;

		while (!Q.empty()){

			int lo = 0, hi = Q.size();

			vector<int> v;

			while (lo++ < hi){

				TreeNode* t = Q.front();

				Q.pop();

				if (t == NULL){

					v.push_back(0);

					continue;

				}

				else{

					v.push_back(t->val);

				}

				if (t->left){

					Q.push(t->left);

				}

				else{

					Q.push(0);

				}

				if (t->right){

					Q.push(t->right);

				}

				else{

					Q.push(0);

				}

			}

			for (int i = 0; i < v.size() / 2; i++){

				if (v[i] != v[v.size() - 1 - i]){

					return false;

				}

			}

		}

		return true;

	}

};