# 【一刷《剑指Offer》】面试题 6：重建二叉树

### 二、分析问题

【经典二叉树问题】

root->left 递归生成。

root->right 递归生成。

### 三、代码

//力扣AC的代码
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* traversal(vector<int>& preorder, int pre_st, int pre_ed, vector<int>& inorder, int in_st, int in_ed)
{
if(pre_st>pre_ed || in_st>in_ed) return nullptr;
TreeNode* root=new TreeNode(preorder[pre_st]);
for(int i=0; i<inorder.size(); i++)
{
if(inorder[i]==preorder[pre_st])
{
root->left=traversal(preorder, pre_st+1, (pre_st+1)+(i-in_st)-1, inorder, in_st, i-1);
root->right=traversal(preorder, (pre_st+1)+(i-in_st-1)+1, pre_ed, inorder, i+1, in_ed);
break;
}
}
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n=preorder.size(), m=inorder.size();
return traversal(preorder, 0, n-1, inorder, 0, m-1);
}
};

//力扣AC的代码（化简）
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* traversal(vector<int>& preorder, int pre_st, int pre_ed, vector<int>& inorder, int in_st, int in_ed)
{
if(pre_st>pre_ed || in_st>in_ed) return nullptr;
TreeNode* root=new TreeNode(preorder[pre_st]);
for(int i=0; i<inorder.size(); i++)
{
if(inorder[i]==preorder[pre_st])
{
root->left=traversal(preorder, pre_st+1, pre_st+i-in_st, inorder, in_st, i-1);
root->right=traversal(preorder, pre_st+i-in_st+1, pre_ed, inorder, i+1, in_ed);
break;
}
}
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n=preorder.size(), m=inorder.size();
return traversal(preorder, 0, n-1, inorder, 0, m-1);
}
};

//牛客AC的代码
/**
* struct TreeNode {
*  int val;
*  struct TreeNode *left;
*  struct TreeNode *right;
*  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param preOrder int整型vector
* @param vinOrder int整型vector
* @return TreeNode类
*/
TreeNode* traversal(vector<int>& preOrder, int pre_st, int pre_ed, vector<int>& vinOrder, int in_st, int in_ed)
{
if(pre_st>pre_ed || in_st>in_ed) return nullptr;
TreeNode* root=new TreeNode(preOrder[pre_st]);
for(int i=0; i<vinOrder.size(); i++)
{
if(vinOrder[i]==preOrder[pre_st])
{
root->left=traversal(preOrder, pre_st+1, pre_st+i-in_st, vinOrder, in_st, i-1);
root->right=traversal(preOrder, pre_st+i-in_st+1, pre_ed, vinOrder, i+1, in_ed);
break;
}
}
return root;
}
TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
int n=preOrder.size(), m=vinOrder.size();
return traversal(preOrder, 0, n-1, vinOrder, 0, m-1);
}
};

## 五、扩展

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* traversal(vector<int>& inorder, int in_st, int in_ed, vector<int>& postorder, int post_st, int post_ed)
{
if(in_st>in_ed || post_st>post_ed) return nullptr;
TreeNode* root=new TreeNode(postorder[post_ed]);
for(int i=0; i<inorder.size(); i++)
{
if(inorder[i]==postorder[post_ed])
{
root->left=traversal(inorder, in_st, i-1, postorder, post_st, post_st+(i-in_st)-1);
root->right=traversal(inorder, i+1, in_ed, postorder, post_st+(i-in_st), post_ed-1);
break;
}
}
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int n=inorder.size(), m=postorder.size();
return traversal(inorder, 0, n-1, postorder, 0, m-1);
}
};

###### 通过先序与后序遍历可以构造二叉树吗？

|
2月前
【一刷《剑指Offer》】面试题 23：从上往下打印二叉树
【一刷《剑指Offer》】面试题 23：从上往下打印二叉树
37 0
|
2月前
【一刷《剑指Offer》】面试题 22：栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22：栈的压入、弹出系列
28 0
|
2月前
|

【一刷《剑指Offer》】面试题 21：包含 main 函数的栈
【一刷《剑指Offer》】面试题 21：包含 main 函数的栈
14 0
|
2月前
【一刷《剑指Offer》】面试题 20：顺时针打印矩阵
【一刷《剑指Offer》】面试题 20：顺时针打印矩阵
39 0
|
2月前
【一刷《剑指Offer》】面试题 19：二叉树的镜像
【一刷《剑指Offer》】面试题 19：二叉树的镜像
24 0
|
2月前
【一刷《剑指Offer》】面试题 18：树的子结构
【一刷《剑指Offer》】面试题 18：树的子结构
29 0
|
2月前
【一刷《剑指Offer》】面试题 17：合并两个排序的链表
【一刷《剑指Offer》】面试题 17：合并两个排序的链表
26 0
|
2月前
【一刷《剑指Offer》】面试题 16：反转链表
【一刷《剑指Offer》】面试题 16：反转链表
31 0
|
2月前
【一刷《剑指Offer》】面试题 15：链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15：链表中倒数第 k 个结点
27 0
|
2月前
|
C++
【一刷《剑指Offer》】面试题 14：调整数组顺序使奇数位于偶数前面
【一刷《剑指Offer》】面试题 14：调整数组顺序使奇数位于偶数前面
28 0