798236606 发表于 2020-2-9 16:44:25

PTA A_1020 Tree Traversals

本帖最后由 798236606 于 2020-2-9 16:43 编辑

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

解：
1.二叉查找树递归插入+广度优先遍历
#include<cstdio>
#include<queue>

using namespace std;

typedef struct node{
    int data;
    struct node *lchild, *rchild;
   
    node()
    {
      lchild = rchild = NULL;
    }
}BTNode, *BTREE;

int n, postorder, inorder;

int find(int target)
{
    for (int i = 0; i < n; i++)
      if (inorder == target)
            return i;
            
    return -1;
}

void insert(BTREE root, int pos)
{
    if (!root) return;
   
    int parents = find(root->data);
   
    if (pos > parents)
    {
      if (root->rchild)
            insert(root->rchild, pos);
      else
      {
            root->rchild = new BTNode;
            root->rchild->data = inorder;
      }
    }
    else
    {
      if (root->lchild)
            insert(root->lchild, pos);
      else
      {
            root->lchild = new BTNode;
            root->lchild->data = inorder;
      }         
    }
}

void BFS(BTREE root)
{
    queue<BTREE> q;
   
    q.push(root);
   
    while (1)
    {
      printf("%d", q.front()->data);
      
      if (q.front()->lchild) q.push(q.front()->lchild);
      if (q.front()->rchild) q.push(q.front()->rchild);
      q.pop();
      
      if (q.empty()) break;

      putchar(' ');
    }
}

int main(void)
{
    scanf("%d", &n);
   
    if (!n) return 0;
   
    for (int i = 0; i < n; i++)
      scanf("%d", postorder + i);
      
    for (int i = 0; i < n; i++)
      scanf("%d", inorder + i);
   
    BTREE root = new BTNode;   
    root->data = postorder;
   
    for (int i = n - 2; i >= 0; i--)
      insert(root, find(postorder));
      
    BFS(root);

    return 0;   
}
2.二叉查找树迭代插入+广度优先遍历
#include<cstdio>
#include<queue>

using namespace std;

typedef struct node{
    int data;
    struct node *lchild, *rchild;

    node()
    {
      lchild = rchild = NULL;
    }
} BTNode, *BTREE;

int n, postorder, inorder;

int find(int target)
{
    for (int i = 0; i < n; i++)
      if (inorder == target)
            return i;

    return -1;
}

void insert(BTREE root, int pos)
{
    if (!root) return;

    BTREE child = new BTNode;
    child->data = inorder;

    while (1)
    {
      if (pos > find(root->data))
      {
            if (root->rchild)
                root = root->rchild;
            else
            {
                root->rchild = child;
                break;
            }
      }
      else
      {
            if (root->lchild)
                root = root->lchild;
            else
            {
                root->lchild = child;
                break;
            }
      }
    }
}

void BFS(BTREE root)
{
    queue<BTREE> q;

    q.push(root);

    while (1)
    {
      printf("%d", q.front()->data);

      if (q.front()->lchild) q.push(q.front()->lchild);
      if (q.front()->rchild) q.push(q.front()->rchild);
      q.pop();

      if (q.empty()) break;

      putchar(' ');
    }
}

int main(void)
{
    scanf("%d", &n);

    if (!n) return 0;

    for (int i = 0; i < n; i++)
      scanf("%d", postorder + i);

    for (int i = 0; i < n; i++)
      scanf("%d", inorder + i);

    BTREE root = new BTNode;
    root->data = postorder;

    for (int i = n - 2; i >= 0; i--)
      insert(root, find(postorder));

    BFS(root);

    return 0;
}
页: [1]
查看完整版本: PTA A_1020 Tree Traversals