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;
}
};