反转二叉树

• 反转的定义如下

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int n;
const int N = 20;
int l[N], r[N];
bool has_father[N];
int root = -1;
vector<int> g_v;

void tree_reverse(int root)
{
  if (root == -1) return;

  tree_reverse(l[root]);
  tree_reverse(r[root]);
  swap(l[root], r[root]);
}

void dfs(int u)
{
  if (u == -1) return;
  dfs(l[u]);
  g_v.push_back(u);
  dfs(r[u]);
}

void bfs()
{
  vector<int> v;
  queue<int> q;
  q.push(root);

  while (q.size())
  {
      int t = q.front();
      q.pop();
      v.push_back(t);
      if (l[t] != -1) q.push(l[t]);
      if (r[t] != -1) q.push(r[t]);
  }

  printf("%d", v[0]);
  for (int i = 1; i < v.size(); i ++ ) printf(" %d", v[i]);
  puts("");
}

int main()
{
  memset(l, -1, sizeof l), memset(r, -1, sizeof r);
  cin >> n;
  for (int i = 0; i < n; i ++ )
  {
      char op1[2], op2[2];
      cin >> op1 >> op2;
      if (*op1 != '-')
      {
          l[i] = *op1 - '0';
          has_father[l[i]] = true;
      }
      if (*op2 != '-')
      {
          r[i] = *op2 - '0';
          has_father[r[i]] = true;
      }
  }

  // 找到root
  while (has_father[++ root]);

  tree_reverse(root);
  bfs();
  dfs(root);
  printf("%d", g_v[0]);
  for (int i = 1; i < n; i ++ ) printf(" %d", g_v[i]);

  return 0;
}