PAT 1102 Invert a Binary Tree[比较简单]-白红宇

PAT 1102 Invert a Binary Tree[比较简单]

阅读量：5971 次

发布时间：2019-06-19

本文共 2921 字，大约阅读时间需要 9 分钟。

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

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:

81 -- -0 -2 7- -- -5 -4 6

Sample Output:

3 7 2 6 4 0 5 16 5 7 4 3 2 0 1

题目大意：给出一颗二叉树，节点数<=10，可以说很少了，将其左右反转，就是原来的左子树变为右子树，递归进行，并且输出反转后的层次遍历和中序遍历。

我的代码：应该是正确的，但是在层次遍历中因为使用了递归，所以不好控制最后的空格，所以全部测试点格式错误0分，也不能通过传参标记来控制吧。那么也就是说不能通过递归来进行了？

#include 
      
       #include 
       #include 
        
         #include 
         
          using namespace std;struct Node{    int father;    int left,right;    Node(){        left=-1;right=-1;father=-1;    }}node[11];int root;void inorder(int r){
    //但是这个怎么去控制最后一个不输出空格呢？哭唧唧啊。    if(node[r].left!=-1)        inorder(node[r].left);    cout<
          
           <<" ";    if(node[r].right!=-1)        inorder(node[r].right);}int main() {    int n;    cin>>n;    char ch1,ch2;    for(int i=0;i
           
            >ch1>>ch2; if(ch1!='-'){ node[i].right=ch1-'0'; node[ch1-'0'].father=i; } if(ch2!='-'){ node[i].left=ch2-'0'; node[ch2-'0'].father=i; } } root=-1; for(int i=0;i

que;//现在完全不知道根是哪一个。 que.push(root); while(!que.empty()){ int top=que.front(); que.pop(); cout<

View Code

#include 
     
      #include 
      #include 
       
        #include 
        
         using namespace std;struct Node{    int father;    int left,right;    Node(){        left=-1;right=-1;father=-1;    }}node[11];int root;vector
         
           in;void inorder(int r){
   //但是这个怎么去控制最后一个不输出空格呢？哭唧唧啊。    if(node[r].left!=-1)        inorder(node[r].left);    in.push_back(r);    if(node[r].right!=-1)        inorder(node[r].right);}int main() {    int n;    cin>>n;    char ch1,ch2;    for(int i=0;i
          
           >ch1>>ch2; if(ch1!='-'){ node[i].right=ch1-'0'; node[ch1-'0'].father=i; } if(ch2!='-'){ node[i].left=ch2-'0'; node[ch2-'0'].father=i; } } root=-1; for(int i=0;i

que;//现在完全不知道根是哪一个。 que.push(root); while(!que.empty()){ int top=que.front(); que.pop(); cout<

//我应该是个智障吧，中序递归遍历直接存到一个向量里，最后在输出，不就好了？不直接在便利的时候输出啊！！。。学习了！

转载于:https://www.cnblogs.com/BlueBlueSea/p/9550394.html