论坛 › C\C++交流 › PTA A_1102 Invert a Binary Tree

798236606 发表于 2020-2-11 16:52:58

PTA A_1102 Invert a Binary Tree

传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805365537882112

解：
二叉树的遍历
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

typedef struct node{
    int lchild, rchild;
} BTNode;

int ttl;

void reverse_tree(int root, BTNode tree[])
{
    if (root == -1) return;

    reverse_tree(tree.lchild, tree);
    reverse_tree(tree.rchild, tree);
   
    int temp = tree.lchild;
    tree.lchild = tree.rchild;
    tree.rchild = temp;
}

void BFS(int root, BTNode tree[])
{
    queue<int> q;

    q.push(root);

    while (!q.empty())
    {
      int index = q.front();
      q.pop();

      printf("%d", index);
      if (--ttl) putchar(' ');

      if (tree.lchild != -1) q.push(tree.lchild);
      if (tree.rchild != -1) q.push(tree.rchild);
    }

    putchar('\n');
}

void print_inorder(int root, BTNode tree[])
{
    if (root == -1) return;

    print_inorder(tree.lchild, tree);
    printf("%d", root);
    if (--ttl) putchar(' ');
    print_inorder(tree.rchild, tree);
}

int main(void)
{
    int n, hash_table = {0};
    BTNode tree;

    memset(tree, -1, sizeof(tree));
   
    scanf("%d", &n);
    if (!n) return 0;
    getchar();
    for (int i = 0; i < n; i++)
    {
      char s;

      fgets(s, 5, stdin);
      if (s != '-') ++hash_table.lchild = s - '0'];
      if (s != '-') ++hash_table.rchild = s - '0'];
    }

    for (int i = 0; i < n; i++)
      if (!hash_table)
      {
            reverse_tree(i, tree);
            ttl = n;
            BFS(i, tree);
            ttl = n;
            print_inorder(i, tree);
            break;
      }

    return 0;
}

查看完整版本: PTA A_1102 Invert a Binary Tree