题目:
Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
Sample Output:
4 1 6 3 5 7 2
代码:
#include<stdio.h> #include<iostream> #include<queue> using namespace std; int n; int pos[32], in[32]; struct Node{ int value; Node* left; Node* right; }; Node* ConstructTree(int posl, int posr, int inl, int inr){ if(posl > posr){ return NULL; } Node* root = new Node; root->value = pos[posr]; int k; for(k = inl; in[k] != pos[posr]; k++); int numLeft = k - inl; root->left = ConstructTree(posl, posl + numLeft - 1, inl, k - 1); root->right = ConstructTree(posl + numLeft, posr - 1, k + 1, inr); return root; } int main(){ scanf("%d", &n); for(int i = 0; i < n; i++){ scanf("%d", &pos[i]); } for(int i = 0; i < n; i++){ scanf("%d", &in[i]); } Node* root = ConstructTree(0, n - 1, 0, n - 1); bool flag = false; queue<Node*> q; q.push(root); while(!q.empty()){ Node* tmp = q.front(); q.pop(); if(flag == true){ printf(" "); }else{ flag = true; } printf("%d", tmp->value); if(tmp->left != NULL){ q.push(tmp->left); } if(tmp->right != NULL){ q.push(tmp->right); } } return 0; }
总结:
将二叉树以层序遍历输出:
queue<Node*> q; q.push(root); while(!q.empty()){ Node* tmp = q.front(); q.pop(); if(flag == true){ printf(" "); }else{ flag = true; } printf("%d", tmp->value); if(tmp->left != NULL){ q.push(tmp->left); } if(tmp->right != NULL){ q.push(tmp->right); } }
根据中序和后序遍历构造二叉树:
Node* ConstructTree(int posl, int posr, int inl, int inr){ if(posl > posr){ return NULL; } Node* root = new Node; root->value = pos[posr]; int k; for(k = inl; in[k] != pos[posr]; k++); int numLeft = k - inl; root->left = ConstructTree(posl, posl + numLeft - 1, inl, k - 1); root->right = ConstructTree(posl + numLeft, posr - 1, k + 1, inr); return root; }
标签:tmp,Node,posl,1020,int,posr,Traversals,Tree,root From: https://www.cnblogs.com/yccy/p/17403965.html