1368：对称二叉树(tree_c)

【算法分析】
        题目给的输入的序列是二叉树的顺序存储结构，设数组tree，tree[i]表示用顺序存储结构保存二叉树第i结点的值。那么输入的第i个字符就是tree[i]的值。这里可以使用每次循环读入一个字符的方法，当读入EOF时停止读入。也可以先读入整个字符串，再做赋值。为tree数组设值。设标志位isSym表示该树是否是对称的。
        遍历整棵树（使用哪种遍历方法都可以），看每个结点的左右孩子，如果左右孩子中有1个是空结点而另一个不是，那么整棵树就不是对称的。遍历完所有结点后，可以确定该树是否是对称的。
       注意在遍历顺序存储结构的树的时候，临时求出的下标可能会很大（因为每次都会乘以2），所以数组尽量开得大一些（比如最后一个结点的地址是1000，那么要把数组长度开成2000多），也可以先记录整个顺序存储结构tree数组中最后一个元素的下标tn，如果访问到的下标超过tn，那么这次访问无意义，直接返回。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
#define N 1005
char tree[N];//树的顺序存储结构，初值都为'\0'，tree[i]:第i结点的值，如果为'\0'表示这里为空。
//tree[2*i]:第i结点的左孩子的值，tree[2*i+1]:第i结点右孩子的值
int tn;//tree数组最后一个元素的下标，应该保证N > 2*tn 
bool isSymmetric(int r)//判断以r为根结点的树是否是对称的 
{
	if(tree[r] == '\0')//如果遍历到空结点，那么是对称的 
		return true;
	if(tree[2*r] == '\0' && tree[2*r+1] != '\0' || 
		tree[2*r] != '\0' && tree[2*r+1] == '\0')//如果左子树空但右子树不空，或右子树空但左子树不空 
		return false;
	return isSymmetric(2*r) && isSymmetric(2*r+1);//左右子树都是对称的，该树才是对称的 
}
int main()
{
	char c;
	while((c = cin.get()) != EOF)//二叉树的顺序存储结构字符串读入tree 
	{
		if(c == '#' || c == '\n')//遇到'#'或换行符，都转为0 
			tree[++tn] = '\0';
		else
			tree[++tn] = c;
	}
	cout << (isSymmetric(1) ? "Yes" : "No");
	return 0;
}