解题思路
这是一道二叉树重建和遍历的综合题目，主要思路如下：
-
问题分析：
- 给定二叉树的层序遍历和中序遍历
- 需要重建二叉树
- 输出叶子节点、先序遍历和后序遍历
- 树的深度不超过10，节点数小于1024
-
解决方案：
- 根据层序和中序遍历重建二叉树
- 使用递归方法构建树结构
- 分别实现三种遍历方法
- 特别处理叶子节点的识别
-
实现细节：
- 使用哈希表存储中序遍历的节点位置
- 递归构建左右子树
- 按要求格式化输出结果
代码
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
private:
unordered_map<int, int> pos;
vector<int> leaves;
vector<int> preorder, postorder;
public:
TreeNode* buildTree(vector<int>& level, vector<int>& inorder) {
// 建立中序遍历的值到位置的映射
for(int i = 0; i < inorder.size(); i++) {
pos[inorder[i]] = i;
}
return construct(level, inorder, 0, inorder.size()-1);
}
TreeNode* construct(vector<int>& level, vector<int>& inorder, int left, int right) {
if(left > right) return NULL;
// 在level中找到第一个在当前中序范围内的值作为根节点
TreeNode* root = NULL;
for(int i = 0; i < level.size(); i++) {
int pos_in_inorder = pos[level[i]];
if(pos_in_inorder >= left && pos_in_inorder <= right) {
root = new TreeNode(level[i]);
root->left = construct(level, inorder, left, pos_in_inorder-1);
root->right = construct(level, inorder, pos_in_inorder+1, right);
break;
}
}
return root;
}
void getLeaves(TreeNode* root) {
if(!root) return;
if(!root->left && !root->right) {
leaves.push_back(root->val);
return;
}
getLeaves(root->left);
getLeaves(root->right);
}
void preOrder(TreeNode* root) {
if(!root) return;
preorder.push_back(root->val);
preOrder(root->left);
preOrder(root->right);
}
void postOrder(TreeNode* root) {
if(!root) return;
postOrder(root->left);
postOrder(root->right);
postorder.push_back(root->val);
}
void printResult(TreeNode* root) {
// 获取所有结果
getLeaves(root);
preOrder(root);
postOrder(root);
// 按格式输出
for(int i = 0; i < leaves.size(); i++) {
cout << leaves[i] << (i == leaves.size()-1 ? "\n" : " ");
}
for(int i = 0; i < preorder.size(); i++) {
cout << preorder[i] << (i == preorder.size()-1 ? "\n" : " ");
}
for(int i = 0; i < postorder.size(); i++) {
cout << postorder[i] << (i == postorder.size()-1 ? "\n" : " ");
}
}
};
int main() {
int n;
vector<int> level, inorder;
// 读入层序遍历
string num;
while(cin >> num && num != "\n") {
level.push_back(stoi(num));
}
// 读入中序遍历
while(cin >> num && num != "\n") {
inorder.push_back(stoi(num));
}
Solution solution;
TreeNode* root = solution.buildTree(level, inorder);
solution.printResult(root);
return 0;
}
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Main {
private Map<Integer, Integer> pos = new HashMap<>();
private List<Integer> leaves = new ArrayList<>();
private List<Integer> preorder = new ArrayList<>();
private List<Integer> postorder = new ArrayList<>();
public TreeNode buildTree(int[] level, int[] inorder) {
// 建立中序遍历的值到位置的映射
for(int i = 0; i < inorder.length; i++) {
pos.put(inorder[i], i);
}
return construct(level, inorder, 0, inorder.length-1);
}
private TreeNode construct(int[] level, int[] inorder, int left, int right) {
if(left > right) return null;
// 在level中找到第一个在当前中序范围内的值作为根节点
TreeNode root = null;
for(int i = 0; i < level.length; i++) {
int posInInorder = pos.get(level[i]);
if(posInInorder >= left && posInInorder <= right) {
root = new TreeNode(level[i]);
root.left = construct(level, inorder, left, posInInorder-1);
root.right = construct(level, inorder, posInInorder+1, right);
break;
}
}
return root;
}
private void getLeaves(TreeNode root) {
if(root == null) return;
if(root.left == null && root.right == null) {
leaves.add(root.val);
return;
}
getLeaves(root.left);
getLeaves(root.right);
}
private void preOrder(TreeNode root) {
if(root == null) return;
preorder.add(root.val);
preOrder(root.left);
preOrder(root.right);
}
private void postOrder(TreeNode root) {
if(root == null) return;
postOrder(root.left);
postOrder(root.right);
postorder.add(root.val);
}
private void printResult(TreeNode root) {
// 获取所有结果
getLeaves(root);
preOrder(root);
postOrder(root);
// 按格式输出叶子节点
for(int i = 0; i < leaves.size(); i++) {
System.out.print(leaves.get(i));
if(i < leaves.size() - 1) System.out.print(" ");
}
System.out.println();
// 输出先序遍历
for(int i = 0; i < preorder.size(); i++) {
System.out.print(preorder.get(i));
if(i < preorder.size() - 1) System.out.print(" ");
}
System.out.println();
// 输出后序遍历
for(int i = 0; i < postorder.size(); i++) {
System.out.print(postorder.get(i));
if(i < postorder.size() - 1) System.out.print(" ");
}
System.out.println();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读入层序遍历
String[] levelStr = sc.nextLine().split(" ");
int[] level = new int[levelStr.length];
for(int i = 0; i < levelStr.length; i++) {
level[i] = Integer.parseInt(levelStr[i]);
}
// 读入中序遍历
String[] inorderStr = sc.nextLine().split(" ");
int[] inorder = new int[inorderStr.length];
for(int i = 0; i < inorderStr.length; i++) {
inorder[i] = Integer.parseInt(inorderStr[i]);
}
Main solution = new Main();
TreeNode root = solution.buildTree(level, inorder);
solution.printResult(root);
sc.close();
}
}
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def __init__(self):
self.pos = {}
self.leaves = []
self.preorder = []
self.postorder = []
def buildTree(self, level, inorder):
# 建立中序遍历的值到位置的映射
for i, val in enumerate(inorder):
self.pos[val] = i
return self.construct(level, inorder, 0, len(inorder)-1)
def construct(self, level, inorder, left, right):
if left > right:
return None
# 在level中找到第一个在当前中序范围内的值作为根节点
root = None
for val in level:
pos_in_inorder = self.pos[val]
if left <= pos_in_inorder <= right:
root = TreeNode(val)
root.left = self.construct(level, inorder, left, pos_in_inorder-1)
root.right = self.construct(level, inorder, pos_in_inorder+1, right)
break
return root
def getLeaves(self, root):
if not root:
return
if not root.left and not root.right:
self.leaves.append(root.val)
return
self.getLeaves(root.left)
self.getLeaves(root.right)
def preOrder(self, root):
if not root:
return
self.preorder.append(root.val)
self.preOrder(root.left)
self.preOrder(root.right)
def postOrder(self, root):
if not root:
return
self.postOrder(root.left)
self.postOrder(root.right)
self.postorder.append(root.val)
def printResult(self, root):
# 获取所有结果
self.getLeaves(root)
self.preOrder(root)
self.postOrder(root)
# 按格式输出
print(" ".join(map(str, self.leaves)))
print(" ".join(map(str, self.preorder)))
print(" ".join(map(str, self.postorder)))
def main():
# 读入层序遍历
level = list(map(int, input().split()))
# 读入中序遍历
inorder = list(map(int, input().split()))
solution = Solution()
root = solution.buildTree(level, inorder)
solution.printResult(root)
if __name__ == "__main__":
main()
算法及复杂度
- 算法：树的重建和遍历
- 时间复杂度：
- 重建树需要在层序遍历中查找
- 空间复杂度：
- 存储树结构和遍历结果
京公网安备 11010502036488号