假设二叉树上各结点的权值互不相同且都为正整数。
给定二叉树的前序遍历和中序遍历,请你输出二叉树的后序遍历序列。
输入格式
第一行包含整数 N,表示二叉树结点总数。
第二行给出二叉树的前序遍历序列。
第三行给出二叉树的中序遍历序列。
输出格式
输出二叉树的后序遍历的第一个数字。
数据范围
1≤N≤50000
输入样例:
7
1 2 3 4 5 6 7
2 3 1 5 4 7 6
输出样例:
3 2 5 7 6 4 1
已知树的先序遍历的第一个元素就是树(子树)的根节点
手动模拟求后序遍历:
- 找先序中第一个数,再看该数在中序遍历中的位置
- 中序位置的左边的数就在该数的左子树上, 右边的数就在该数的右子树上
- 再看该数的先序中 左子树上的数离该数最近的 和 右子树上的数离该数最近的 ,
这两个离得最近得数就是该数的左右子树的根节点
代码解读
代码中的build函数传递的是 先序和后序序列的左右闭区间
找到左右子树的左右闭区间, 每次取先序的第一个数就可以完成上述手动模拟操作,构建出完整的树
先序的左右闭区间不会找的话看下面的图