1102. Invert a Binary Tree (25)1102. Invert a Binary Tree (25)
The following is from Max Howell @twitter:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
Now it’s your turn to prove that YOU CAN invert a binary tree!
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<=10) which is the total number of nodes in the tree – and hence the nodes are numbered from 0 to N-1. Then N lines follow, each corresponds to a node from 0 to N-1, and gives the indices of the left and right children of the node. If the child does not exist, a “-” will be put at the position. Any pair of children are separated by a space.
Output Specification:
For each test case, print in the first line the level-order, and then in the second line the in-order traversal sequences of the inverted tree. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.
Sample Input:
8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6
Sample Output:
3 7 2 6 4 0 5 1
6 5 7 4 3 2 0 1
分析
- 题目很简单，简单的我以为一下AC呢，万万没想到，被第二个测试点卡住了，并且卡了很久，试了一些例子还都对，其原因是初始化工作没做对，见代码注释部分。
错误的分析：最开始想的是，有一种情况，有几个结点没用，既没有父亲又没有孩子，这种结点我们是不计入的，因为题目所说为二叉树，并不是森林。测试点二没过的原因是，根结点没找对（入坑原因：寻找时的初始结点可能就是我们要抛弃的那个，就会导致根结点没找对）。结论：数据果然都用上了，不是题目的问题，是自己初始化整合到建树的工作上，导致了混乱。
//初始化工作导致错误。 input 3 1 - 2 - - - right output 0 1 2 0 1 2 wrong output(原因，见代码注释) 1 2 1 2总结：初始化工作分离，单独出来。
code
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int l[15];
int r[15];
int n[15];
vector<vector<int>>out;
//层遍历（R->L）
void level(int i,int d)
{if(out.size()<=d){vector<int> tmp;tmp.push_back(i);out.push_back(tmp);}elseout[d].push_back(i);if(r[i]!=-1)level(r[i],d+1);if(l[i]!=-1)level(l[i],d+1);
}
//RNL遍历
void in(int i,int last)
{if(r[i]!=-1){in(r[i],last);}cout<<i;n[i]=-1;if(last!=i)cout<<" ";elsecout<<endl;if(l[i]!=-1){in(l[i],last);}
}
int main()
{int count=0;string tmp;int head=0;cin>>count;//独立出来的初始化工作。for(int i=0;i<15;i++){l[i]=r[i]=n[i]=-1;}for(int i=0;i<count;i++){//在这是有问题的：孩子的序号比父亲大，这是会操作 n[c]=i,是孩子的父亲指向当前，//但到i==c那是，又会对其父亲结点初始化，置为-1，导致错误。//结论：初始化工作单独出来，不要增加麻烦整合到别的地方//l[i]=-1;//r[i]=-1;//n[i]=-1;cin>>tmp;if(tmp!=string("-")){l[i]=stoi(tmp,nullptr,0);n[l[i]]=i;head=i;}cin>>tmp;if(tmp!=string("-")){r[i]=stoi(tmp,nullptr,0);n[r[i]]=i;head=i;}}//find headwhile(true){if(n[head]==-1){break;}elsehead=n[head];}level(head,0);for(int i=0;i<out.size();i++){for(int j=0;j<out[i].size();j++){cout<<out[i][j];if(j==out[i].size()-1)if(i==out.size()-1){cout<<endl;break;}cout<<" ";}}int ll=head;while(true){if(l[ll]==-1){break;}elsell=l[ll];}in(head,ll);return 0;
}