P1827 【[USACO3.4]美国血统 American Heritage】 题解
原题链接： P1827 【美国血统 American Heritage】
题意简述： 输入一棵二叉树的先序遍历和中序遍历序列，输出后序遍历序列。
前置知识： 二叉树遍历
定义： 所谓遍历(\(Traversal\))是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。
实现：
| 前序遍历(\(Preorder Traversal)\) | 中序遍历(\(Inorder Traversal\)) | 后序遍历(Postorder Traversal) | |
|---|---|---|---|
| \(step\) 1. | 访问根结点 | 遍历左子树 | 遍历左子树 |
| \(step\) 2. | 遍历左子树 | 访问根结点 | 遍历右子树 |
| \(step\) 3. | 遍历右子树 | 遍历右子树 | 访问根结点 |
思路：边建树（递归）边输出。后序序列输出时应该将输出放在两个递归函数后面，不难。不过还有些细节还是需要注意，比如传参的时候左右子树分别在先序和中序的位置需要注意。
\(end\)