1102 Invert a Binary Tree (25 分)

思路

翻转二叉树
后序遍历翻转即可，由于给出每个结点的左右儿子，所以这里用到二叉树的静态写法更加方便

这里有个坑，bool数组初始化为false才是有效的，别的效果不行，暂时不知道为什么

代码

#include<bits/stdc++.h>
using namespace std;const int maxn = 30;struct node{  //二叉树的静态写法，更简单实现int lchild,rchild;
}Node[maxn];bool isRoot[maxn]={false};
int n,num=0;void post_reverse(int root)
{if(Node[root].lchild!=-1)post_reverse(Node[root].lchild);if(Node[root].rchild!=-1)post_reverse(Node[root].rchild);int change = Node[root].lchild;Node[root].lchild  =  Node[root].rchild;Node[root].rchild = change;
}void pre_traverse(int root)
{if(Node[root].lchild!=-1)pre_traverse(Node[root].lchild);num+=1;if(num==n)cout<<root;elsecout<<root<<" ";if(Node[root].rchild!=-1)pre_traverse(Node[root].rchild);
}void level_traverse(int root)
{queue<int>Q;Q.push(root);while(!Q.empty()){int nnn = Q.front();Q.pop();if(Node[nnn].lchild!=-1)Q.push(Node[nnn].lchild);if(Node[nnn].rchild!=-1)Q.push(Node[nnn].rchild);num+=1;if(num==n)cout<<nnn;elsecout<<nnn<<" ";}
}
int main()
{cin>>n;char ch;for(int i=0;i<n;i++){cin>>ch;if(ch=='-'){Node[i].lchild = -1;}else{int input = ch-'0';Node[i].lchild = input;isRoot[input] =true;}cin>>ch;if(ch=='-'){Node[i].rchild = -1;}else{int input = ch-'0';Node[i].rchild = input;isRoot[input] =true;}}int root;for(int i=0;i<n;i++){if(!isRoot[i])root=i;}post_reverse(root);num = 0;level_traverse(root);cout<<endl;num = 0;pre_traverse(root);}