PAT1102 Invert a Binary Tree倒置二叉树-蒲公英云

PAT1102 Invert a Binary Tree倒置二叉树

忘是亡心i 2023-05-21 05:59 38阅读 0赞

在这里插入图片描述
思路：
很常规的建树遍历问题，按照题目输入在读数据的直接建树，因为根节点不是任何结点的孩子，所以那个没有出现过的点就是根节点
本题的遍历过程比较特殊，右孩子的优先级大于左孩子，对于层序遍历，只需要先判断右孩子在判断左孩子即可
同样的，对于中序遍历，应采用右孩子根左孩子的顺序

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct node{ 
  int data;
  int left,right;
}Node[15];
vector<int> in,lv;
void inorder(int root)
{ 
  if(root==-1)return;
  inorder(Node[root].right);
  in.push_back(Node[root].data);
  inorder(Node[root].left);
}
void bfs(int root)
{ 
  queue<node> q;
  q.push(Node[root]);
  while(!q.empty())
  { 
    node it=q.front();
    q.pop();
    lv.push_back(it.data);
    if(it.right!=-1)q.push(Node[it.right]);
    if(it.left!=-1)q.push(Node[it.left]);
  }
}
int main()
{ 
  int n,root;
  vector<int> hash(10,0);//0表示未出现过
  cin>>n;
  for(int i=0;i<n;i++)
  { 
    char a,b;
    Node[i].data=i;
    cin>>a>>b;
    if(a!='-')
    { 
      Node[i].left=a-'0';
      hash[a-'0']=1;
    }
    else Node[i].left=-1;
    if(b!='-')
    { 
      Node[i].right=b-'0';
      hash[b-'0']=1;
    }
    else Node[i].right=-1;
  }
  for(int i=0;i<n;i++)
  { 
    if(hash[i]==0)root=i;
  }
  inorder(root);
  bfs(root);
  for(int i=0;i<n;i++)
  { 
    cout<<lv[i]<<(i!=n-1?" ":"\n");
  }
  for(int i=0;i<n;i++)
  { 
    cout<<in[i]<<(i!=n-1?" ":"\n");
  }
  return 0;
}