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:Sample Output:
- 8
- 1 -
- - -
- 0 -
- 2 7
- - -
- - -
- 5 -
- 4 6
- 3 7 2 6 4 0 5 1
- 6 5 7 4 3 2 0 1
- #include <iostream>
- #include<stdio.h>
- #include<algorithm>
- #include<string>
- #include<vector>
- #include<queue>
- using namespace std;
- struct Node{
- int lchild;
- int rchild;
- int parent;
- Node() :lchild(-1),rchild(-1),parent(-1){}
- //因为不是用Node*,所以不能用是否等于NULL来判断
- //所以这里初始化全部用-1,方便用来判断
- }buf[10];
- int findRoot(int x){//找到根节点
- if (buf[x].parent != -1){
- return findRoot(buf[x].parent);
- }
- return x;
- }
- vector<int>ans;//为了答案的格式化输出,所以用一个vector存储顺序
- void level_order(int root){//层序遍历,需要和queue配合使用
- queue<int>Q;
- Q.push(root);
- while (!Q.empty()){
- int cur = Q.front();
- ans.push_back(cur);
- Q.pop();
- if (buf[cur].lchild != -1)
- Q.push(buf[cur].lchild);
- if (buf[cur].rchild != -1)
- Q.push(buf[cur].rchild);
- }
- }
- void in_order(int root){//中序遍历,先左再存储再右
- if (buf[root].lchild != -1)
- in_order(buf[root].lchild);
- ans.push_back(root);
- if (buf[root].rchild != -1)
- in_order(buf[root].rchild);
- }
- void print(vector<int> Vx){//对于vector的格式化输出
- for (int i = 0; i < Vx.size(); ++i){
- if(i) cout << " " << Vx[i];
- else cout << Vx[i];
- }
- }
- int main(){
- //freopen("F://Temp/input.txt","r",stdin);
- int n;
- cin >> n;
- for (int i = 0; i < n; i++){
- string l,r;
- cin >> r >> l;//point,先右后左可以直接实现invert树的效果
- if (r != "-"){
- buf[i].rchild = atoi(r.c_str());//孩子和父的两边都要互相记录
- buf[atoi(r.c_str())].parent = i;
- }
- if (l != "-"){
- buf[i].lchild = atoi(l.c_str());
- buf[atoi(l.c_str())].parent = i;
- }
- }
- int root = findRoot(0);//找到根节点
- ans.clear();
- level_order(root);
- print(ans);
- ans.clear();//记得要清空一下
- cout << endl;
- in_order(root);
- print(ans);
- cout << endl;
- return 0;
- }