1020 tree traversals (25 分)

这道题目是一道关于树的遍历的题目，需要我们实现三种不同的遍历方式：前序遍历、中序遍历和后序遍历。我们需要根据给定的树的结构，按照不同的遍历方式输出遍历结果。这道题目的难点在于如何正确地遍历树，并且输出正确的结果。我们可以使用递归的方式来实现树的遍历，具体实现方法可以参考题目描述中的示例代码。

相关问题

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

binary tree traversals

二叉树遍历是指按照一定的顺序访问二叉树中的所有节点。常见的二叉树遍历方式有前序遍历、中序遍历和后序遍历。前序遍历是先访问根节点，然后访问左子树，最后访问右子树；中序遍历是先访问左子树，然后访问根节点，最后访问右子树；后序遍历是先访问左子树，然后访问右子树，最后访问根节点。除此之外，还有层序遍历，即按照层次顺序从上到下、从左到右访问二叉树中的所有节点。