tree traversals again

树遍历是指遍历树中所有节点的过程。常见的树遍历方法有三种：先序遍历、中序遍历和后序遍历。

- 先序遍历：先访问根节点，再遍历左子树，最后遍历右子树。

- 中序遍历：先遍历左子树，再访问根节点，最后遍历右子树。

- 后序遍历：先遍历左子树，再遍历右子树，最后访问根节点。

相关问题

03-树3 tree traversals again

题目描述：

给定一棵树的中序遍历和后序遍历，请输出它的先序遍历。

输入格式：

第一行包含整数n，表示树中节点的个数。

第二行包含n个整数，表示树的中序遍历结果。

第三行包含n个整数，表示树的后序遍历结果。

输出格式：

输出一行，表示树的先序遍历结果。

输入样例：

5
3 1 4 2 5
3 4 5 2 1

输出样例：

1 3 2 4 5

解题思路：

这道题可以利用树的性质，通过中序遍历和后序遍历重建出一颗二叉树，然后进行先序遍历即可。

首先，后序遍历的最后一个节点为根节点，然后在中序遍历中找到根节点的位置，这样就可以将树分成左子树和右子树，对左右子树分别递归进行建树，最后对根节点进行处理即可。

具体细节见代码实现。

03-树3 tree traversals again (25 分)

题目描述

给定一棵二叉树的中序遍历和后序遍历，你的任务是输出其层序遍历的序列。

输入格式

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出二叉树的中序遍历序列，由不同数字和一个空格隔开。第三行给出其后序遍历序列，格式与中序遍历序列相同。

输出格式

输出一行，把按层序遍历得到的结点的数字按照1~N的顺序依次输出，数字间有1个空格分隔，行末不能有多余空格。

输入样例

7
2 3 1 5 7 6 4
3 2 7 6 4 5 1

输出样例

1 2 4 3 5 6 7

算法1

(递归) $O(n^2)$

1.根据后序遍历的最后一个元素，可以确定根节点
2.根据中序遍历，可以确定左右子树的节点个数
3.递归构建左右子树

时间复杂度

参考文献

python3 代码

算法2

(迭代) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
TreeNode* cur = root;
while(cur || !st.empty()){
while(cur){
st.push(cur);
cur = cur->left;
}
cur = st.top();
st.pop();
res.push_back(cur->val);
cur = cur->right;
}
return res;
}
};