1138 Postorder Traversal
1138 Postorder Traversal
Suppose that all the keys in a binary tree are distinct positive integers. Given the preorder and inorder traversal sequences, you are supposed to output the first number of the postorder 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 (≤ 50,000), the total number of nodes in the binary tree. The second line gives the preorder 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 first number of the postorder traversal sequence of the corresponding binary tree.
Sample Input:
7
1 2 3 4 5 6 7
2 3 1 5 4 7 6
Sample Output:
3
由前序和中序转后序
参考代码:
#include<iostream>
#include<vector>
using namespace std;
vector<int>preOrder, inOrder;
int flag = 1;
void solve(int root, int inl, int inr) {
if (inl >= inr)
return;
int i = inl;
while (i < inr&&inOrder[i] != preOrder[root]) { i++; }
int l = i - inl;
solve(root + 1, i - l, i);
solve(root + 1 + l, i + 1, inr);
if (flag) {
cout << preOrder[root];
flag = 0;
}
}
int main(){
int n;
scanf_s("%d", &n);
preOrder.resize(n);
inOrder.resize(n);
for(int i = 0; i<n; i++) scanf_s("%d",&preOrder[i]);
for(int i = 0; i<n; i++) scanf_s("%d", &inOrder[i]);
solve(0, 0, n);
return 0;
}
上一篇: phpize的深入理解
推荐阅读
-
1138 Postorder Traversal
-
1138 Postorder Traversal
-
js Element Traversal规范中的元素遍历方法
-
1138:将字符串中的小写字母转换成大写字母
-
tree traversal (树的遍历) - 中序遍历 (inorder traversal) - 二叉树的中序遍历
-
tree traversal (树的遍历) - 前序遍历 (preorder traversal) - 二叉树的前序遍历
-
tree traversal (树的遍历) - 前序遍历 (preorder traversal) - 对称二叉树
-
巧用TreeSet求解第k小整数(洛谷P1138题题解,Java语言描述)
-
leecode每日一题01- Binary Tree Level Order Traversal [Medium]
-
Binary Tree Postorder Traversal