Skip to content

Latest commit

 

History

History
182 lines (156 loc) · 5.08 KB

hdu1710(二叉树已知两序求一序).MD

File metadata and controls

182 lines (156 loc) · 5.08 KB
Raw

日期 2022 / 03 / 28

题目

Binary Tree Traversals

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2198 Accepted Submission(s): 964

Problem Description A binary tree is a finite set of vertices that is either empty or consists of a root r and two disjoint binary trees called the left and right subtrees. There are three most important ways in which the vertices of a binary tree can be systematically traversed or ordered. They are preorder, inorder and postorder. Let T be a binary tree with root r and subtrees T1,T2. In a preorder traversal of the vertices of T, we visit the root r followed by visiting the vertices of T1 in preorder, then the vertices of T2 in preorder. In an inorder traversal of the vertices of T, we visit the vertices of T1 in inorder, then the root r, followed by the vertices of T2 in inorder. In a postorder traversal of the vertices of T, we visit the vertices of T1 in postorder, then the vertices of T2 in postorder and finally we visit r. Now you are given the preorder sequence and inorder sequence of a certain binary tree. Try to find out its postorder sequence.

Input

The input contains several test cases. The first line of each test case contains a single integer n (1<=n<=1000), the number of vertices of the binary tree. Followed by two lines, respectively indicating the preorder sequence and inorder sequence. You can assume they are always correspond to a exclusive binary tree.

Output

For each test case print a single line specifying the corresponding postorder sequence.

Sample Input

9 1 2 4 7 3 5 8 9 6

4 7 2 1 8 5 9 3 6

Sample Output

7 4 2 8 9 5 6 3 1

解题思路

这个题目是已知二叉树的先序和中序求后序，由于我们知道二叉树先序遍历中访问顺序是根左右，而中序遍历中访问顺序是左根右，由此我们可以区分出左子树和右子树的序列，例如先序 遍历是1 2 4 7 3 5 8 9 6中序遍历是4 7 2 (1) 8 5 9 3 6可以看出1的左端是左子树，右端是右子树，进行递归我们可以构造出二叉树，从而进行后序遍历的输出,需要注意的是 已知先序后序是不能推导出中序的，因为没有办法确认左子树以及右子树.下面是两种情况的序列推导.

#include <bits/stdc++.h>   //已知先序中序求后序

#define INF 0x7fffffff
#define rep(x, y, z) for (int x = y; x <= z; x++)
#define dec(x, y, z) for (int x = y; x >= z; x--)
#define format(a) memset (a, 0, sizeof(a))
#define swap(a, b) (a ^= b ^= a ^= b)
#define ll long long int
#define ull unsigned long long int 
#define uint unsigned int
const int maxn = 1e6 + 10;
using namespace std;

int pre[maxn];
int in[maxn];

typedef struct tree {
  int data;
  tree *l;
  tree *r;
} tree;

tree *root;

tree *create_tree(int *pre, int *in, int n) {
  tree *s;
  for (int i = 0; i < n; i++) {
    if (pre[0] == in[i]) {
      s = (tree *)malloc(sizeof(tree));   // 分配内存空间
      s->data = in[i]; 
      s->l = create_tree(pre + 1, in, i);  //构建左子树
      s->r = create_tree(pre + i + 1, in + i + 1, n - i - 1);   //构建右子树
      return s;
    }	
  }
  return NULL;
}

void Print(tree *h) {  // 输出后序遍历
  if (h != NULL) {
    Print(h->l);
    Print(h->r);
    if (h == root) {
      cout << h->data << endl;
    } else {
      cout << h->data << ' ';
    }
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  while (cin >> n) {
    root = NULL;  // 将根节点设置为空值
    for (int i = 0; i < n; i++) {
      cin >> pre[i];  // 输入先序序列
    }	
    for (int i = 0; i < n; i++) {
      cin >> in[i];  // 输入中序序列
    }
    root = create_tree(pre, in, n);  // 开始建树
    Print(root);
  } 
  return 0;
}
#include <bits/stdc++.h>   //已知中序后序求先序
 
#define INF 0x7fffffff
#define rep(x, y, z) for (int x = y; x <= z; x++)
#define dec(x, y, z) for (int x = y; x >= z; x--)
#define format(a) memset (a, 0, sizeof(a))
#define swap(a, b) (a ^= b ^= a ^= b)
#define ll long long int
#define ull unsigned long long int 
#define uint unsigned int
const int maxn = 1e6 + 10;
using namespace std;

int in[maxn];
int aft[maxn];

typedef struct tree {
  int data;
  tree *l;
  tree *r;
} tree;

tree *root;

tree *create_tree(int *in, int *aft, int n) {
  tree *s;
  for (int i = 0; i < n; i++) {
    if (in[i] == aft[n - 1]) {
      s = (tree *)malloc(sizeof(tree));
      s->data = in[i];
      s->l = create_tree(in, aft, i);
      s->r = create_tree(in + i + 1, aft + i, n - i - 1);
      return s;
    }	
  }
  return NULL;
}

void Print(tree *h) {  // 输出先序遍历
  if (h == NULL) {
    return;	
  }	
  cout << h->data << ' ';
  Print(h->l);
  Print(h->r);
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  while (cin >> n) {
    root = NULL;
    for (int i = 0; i < n; i++) {
      cin >> in[i];
    }
    for (int i = 0; i < n; i++) {
      cin >> aft[i];
    }
    root = create_tree(in, aft, n);
    Print(root);
  }	 
  return 0;
}