对称二叉树_如果二叉树的左右子树的结构是对称的,即两棵子树皆为空,或者皆不空,则称该二叉树

题目

如果二叉树的左右子树的结构是对称的，即两颗子树皆为空，或者皆不为空，则称该二叉树是对称的。编程判断给定的二叉树是否对称。

例：如图中的二叉树T1是对称的，T2是不对称的。

二叉树用顺序结构给出，若读到#则为空，二叉树T1=ABCDE,T2=ABCD#E,如果二叉树是对称的，输出“Yes",反之输出”No".

样例

样例输入1

ABCDE

样例输出1

Yes

 一开始，乍一看，不就是二叉树吗？判断一下节点数量符不符合要求，再看空位合不合理不就好了吗，然后就狂敲代码，打出了这段代码

#include<bits/stdc++.h>
using namespace std;
string a;
long long p(int n){
	long long sum=1;
	for(int i=1;i<=n;i++){
		sum*=2;
	}
	return sum;
}
int main(){
	cin>>a;
	long long sum=0,len=a.size()-1;
	if(len%2==1){
		cout<<"No";
		return 0;
	}else{
		if(a.find('#')!='#'){
			for(int i=1;i<=len;i+=2){
				if((a[i]=='#'&&a[i+1]!='#')||(a[i]!='#'&&a[i]=='#')){
					cout<<"No";
					return 0;
				}
			}
		}
	for(int i=1;len>0;i++){
		int u=p(i);
		if(len-u<0){
			int y=len;
			for(;y!=1;){
				if(y%2==1){
					break;
				}
				else{
					y/=2;
				}
			}
			if(y!=1){
				cout<<"No";
				return 0;
			}
		}
			len-=u;
	}
		cout<<"Yes";}
}

问题是

 仔细想想我刚刚思路与代码，你有没有发现什么区别呢？

我为什么要去判断字符串长度合不合理呢？

既然空位都标出来了，那判断空位合不合理不就好了

说具体点，就是判断每个子树是不是完整的，不完整，他就不是对称二叉树

Code

#include<bits/stdc++.h>
using namespace std;
string a;
int main()
{
	cin>>a;
	long long sum=0,len=a.size()-1;
	if(a[len]=='#'||len%2==1) {
		cout<<"No";
		return 0;
	} else {
		if(a.find('#')!='#') {
			for(int i=1; i<=len; i+=2) {
				if((a[i]=='#'&&a[i+1]!='#')||(a[i]!='#'&&a[i]=='#')) {
					cout<<"No";
					return 0;
				}
			}
		}
	
	}
	cout<<"Yes";
}