[编程题]重建二叉树

# 1645个回答

```public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
return root;
}
//前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {

if(startPre>endPre||startIn>endIn)
return null;
TreeNode root=new TreeNode(pre[startPre]);

for(int i=startIn;i<=endIn;i++)
if(in[i]==pre[startPre]){
root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
break;
}

return root;
}
}```

# python solution:

```class Solution:
def reConstructBinaryTree(self, pre, tin):
if not pre or not tin:
return None
root = TreeNode(pre.pop(0))
index = tin.index(root.val)
root.left = self.reConstructBinaryTree(pre, tin[:index])
root.right = self.reConstructBinaryTree(pre, tin[index + 1:])
return root```

```/**

* Definition for binary tree

* struct TreeNode {

*     int val;

*     TreeNode *left;

*     TreeNode *right;

*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

*/

class Solution {

public:

struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {

int inlen=in.size();

if(inlen==0)

return NULL;

vector<int> left_pre,right_pre,left_in,right_in;

//创建根节点，根节点肯定是前序遍历的第一个数

//找到中序遍历根节点所在位置,存放于变量gen中

int gen=0;

for(int i=0;i<inlen;i++)

{

if (in[i]==pre[0])

{

gen=i;

break;

}

}

//对于中序遍历，根节点左边的节点位于二叉树的左边，根节点右边的节点位于二叉树的右边

//利用上述这点，对二叉树节点进行归并

for(int i=0;i<gen;i++)

{

left_in.push_back(in[i]);

left_pre.push_back(pre[i+1]);//前序第一个为根节点

}

for(int i=gen+1;i<inlen;i++)

{

right_in.push_back(in[i]);

right_pre.push_back(pre[i]);

}

//和shell排序的思想类似，取出前序和中序遍历根节点左边和右边的子树

//递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点

}

};

```

```import java.util.*;
/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length == 0||in.length == 0){
return null;
}
TreeNode node = new TreeNode(pre[0]);
for(int i = 0; i < in.length; i++){
if(pre[0] == in[i]){
node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1,in.length));
}
}
return node;
}
}```

```function reConstructBinaryTree(pre, vin)
{
if(pre.length==0||vin.length==0){
return null;
};
//前序第一个为根节点 也是中序左右子树的分割点
var index=vin.indexOf(pre[0]);
var left=vin.slice(0,index);//中序左子树
var right=vin.slice(index+1);//中序右子树
return {
val:pre[0],
//递归左右子树的前序，中序
left:reConstructBinaryTree(pre.slice(1,index+1),left),
right:reConstructBinaryTree(pre.slice(index+1),right)
};
}```

```function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
}

function reConstructBinaryTree(pre, vin)
{
if(vin.length === 0)
return null;

var root = 0, i, j;
var left_pre = [], right_pre = [], left_in = [], right_in = [];

for(i = 0; i < vin.length; i++){
if(vin[i] === pre[0]){
root = i;
break;
}
}
for(j = 0; j < root; j++){
left_pre.push(pre[j+1]);
left_in.push(vin[j]);
}
for(j = root + 1; j < vin.length; j++){
right_pre.push(pre[j]);
right_in.push(vin[j]);
}

}
module.exports = {
reConstructBinaryTree : reConstructBinaryTree
};```

python赛高
```class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
if len(pre) == 0:
return None
elif len(pre) == 1:
return TreeNode(pre[0])
else:
ans = TreeNode(pre[0])
ans.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1], tin[:tin.index(pre[0])])
ans.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:], tin[tin.index(pre[0])+1:])
return ans```

```public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return reConBTree(pre,0,pre.length-1,in,0,in.length-1);
}
public TreeNode reConBTree(int [] pre,int preleft,int preright,int [] in,int inleft,int inright){
if(preleft > preright || inleft> inright)//当到达边界条件时候返回null
return null;
//新建一个TreeNode
TreeNode root = new TreeNode(pre[preleft]);
//对中序数组进行输入边界的遍历
for(int i = inleft; i<= inright; i++){
if(pre[preleft] == in[i]){
//重构左子树，注意边界条件
root.left = reConBTree(pre,preleft+1,preleft+i-inleft,in,inleft,i-1);
//重构右子树，注意边界条件
root.right = reConBTree(pre,preleft+i+1-inleft,preright,in,i+1,inright);
}
}
return root;
}
}```

```public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
int i=0;
if(pre.length!=in.length||pre.length==0||in.length==0)
return null;
TreeNode root = new TreeNode(pre[0]);
while(in[i]!=root.val)
i++;
int[] preLeft = new int[i];
int[] inLeft = new int[i];
int[] preRight = new int[pre.length-i-1];
int[] inRight = new int[in.length-i-1];
for(int j = 0;j<in.length;j++) {
if(j<i) {
preLeft[j] = pre[j+1];
inLeft[j] = in[j];
} else if(j>i) {
preRight[j-i-1] = pre[j];
inRight[j-i-1] = in[j];
}
}
root.left = reConstructBinaryTree(preLeft,inLeft);
root.right = reConstructBinaryTree(preRight,inRight);
return root;
}
}```

1.先求出根节点（前序序列第一个元素）。
2.将根节点带入到中序遍历序列中求出左右子树的中序遍历序列。
3.通过左右子树的中序序列元素集合带入前序遍历序列可以求出左右子树的前序序列。
4.左右子树的前序序列第一个元素分别是根节点的左右儿子
5.求出了左右子树的4种序列可以递归上述步骤
```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
//判定递归终止条件；
if(pre.size() == 0 || in.size() == 0) {
return NULL;
}
//定义Node节点并其求根节点；
int root = pre[0];
TreeNode* node = new TreeNode(root);
vector<int>::iterator it;
//1.求左右子树的遍历序列；
vector<int> preLeft, preRight, inLeft, inRight;
//（1）.求根节点在中序遍历序列中的位置；
vector<int>::iterator i;
for(it = in.begin(); it != in.end(); it++) {
if(root == *it) {
i = it;
}
}
//（2）.求左右子树的中序遍历子序列；
int k = 0;
for(it = in.begin(); it != in.end(); it++) {
if(k == 0) {
inLeft.push_back(*it);
}
else if(k == 1) {
inRight.push_back(*it);
}
else {}
if(it == i) {
k = 1;
}
}
//（3）.求左右子树的前序遍历子序列；
k = 0;
vector<int>::iterator ite;
for(it = pre.begin()+1; it != pre.end(); it++) {
for(ite = inLeft.begin(); ite != inLeft.end(); ite++) {
if(*it == *ite) {
preLeft.push_back(*it);
k = 1;
}
}
if(k == 0) {
preRight.push_back(*it);
}
k = 0;
}
//根据遍历序列求出跟的左右节点；
node->left = reConstructBinaryTree(preLeft,inLeft);
node->right = reConstructBinaryTree(preRight,inRight);
//返回节点地址；
return node;
}
};```

```
/* 先序遍历第一个位置肯定是根节点node，

中序遍历的根节点位置在中间p，在p左边的肯定是node的左子树的中序数组，p右边的肯定是node的右子树的中序数组

另一方面，先序遍历的第二个位置到p，也是node左子树的先序子数组，剩下p右边的就是node的右子树的先序子数组

把四个数组找出来，分左右递归调用即可

*/

class Solution {

public:

struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {

int in_size = in.size();

if(in_size == 0)

return NULL;

vector<int> pre_left, pre_right, in_left, in_right;

int val = pre[0];

TreeNode* node = new TreeNode(val);//root node is the first element in pre

int p = 0;

for(p; p < in_size; ++p){

if(in[p] == val) //Find the root position in in

break;

}

for(int i = 0; i < in_size; ++i){

if(i < p){

in_left.push_back(in[i]);//Construct the left pre and in

pre_left.push_back(pre[i+1]);

}

else if(i > p){

in_right.push_back(in[i]);//Construct the right pre and in

pre_right.push_back(pre[i]);

}

}

node->left = reConstructBinaryTree(pre_left, in_left);

node->right = reConstructBinaryTree(pre_right, in_right);

return node;

}

};

```

## 标准C++解法

``````/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
int n = pre.size();
int m = vin.size();
if(n!=m || n == 0)
return NULL;
return construct(pre, vin, 0, n-1, 0, m-1);
}

TreeNode* construct(vector<int>& pre, vector<int>& vin, int l1, int r1, int l2, int r2)
{
TreeNode* root = new TreeNode(pre[l1]);
if(r1 == l1)
{
return root;
}
int val = pre[l1];
int index;
for(index = l2; index <= r2; index ++)
{
if(vin[index] == val)
break;
}
int left_tree_len  = index - l2;
int right_tree_len = r2 - index;
if(left_tree_len > 0)
root->left = construct(pre, vin, l1+1, l1+left_tree_len, l2, index-1);
if(right_tree_len >0 )
root->right = construct(pre, vin, l1+1+left_tree_len, r1, index+1, r2);
return root;
}
};
``````

Here is my Solution.
```/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
import java.util.ArrayList;
import java.util.List;

public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
ArrayList<Integer> preList = new ArrayList<Integer>(pre.length);
ArrayList<Integer> inList = new ArrayList<Integer>(in.length);
for (int i : pre)
for (int i : in)
return getRootNode(preList, inList);
}

private TreeNode getRootNode(List<Integer> preList, List<Integer> inList) {
if (preList.size() == 0)
return null;
int rootVal = preList.get(0);
TreeNode root = new TreeNode(rootVal);
int index = inList.indexOf(rootVal);
List<Integer> leftInList = inList.subList(0, index);
List<Integer> rightInList = inList.subList(index+1, inList.size());
List<Integer> leftPreList = preList.subList(1, leftInList.size()+1);
List<Integer> rightPreList = preList.subList(preList.size()
- rightInList.size(), preList.size());

root.left = getRootNode(leftPreList, leftInList);
root.right = getRootNode(rightPreList, rightInList);

return root;
}
}

```

```class Solution {
public:
struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
if (pre.size() == 0) {
return NULL;
} else if (pre.size() == 1) {
return new TreeNode(pre[0]);
}
TreeNode* root = new TreeNode(pre[0]);
int pos = std::find(in.begin(), in.end(), pre[0]) - in.begin();
vector<int> l_pre = vector<int>(pre.begin() + 1, pre.begin() + pos + 1);
vector<int> l_in = vector<int>(in.begin(), in.begin() + pos);
vector<int> r_pre = vector<int>(pre.begin() + pos + 1, pre.end());
vector<int> r_in = vector<int>(in.begin() + pos + 1, in.end());
root->left = reConstructBinaryTree(l_pre, l_in);
root->right = reConstructBinaryTree(r_pre, r_in);
return root;
}
};```

```
/* 先序遍历第一个位置肯定是根节点node，

中序遍历的根节点位置在中间p，在p左边的肯定是node的左子树的中序数组，p右边的肯定是node的右子树的中序数组

另一方面，先序遍历的第二个位置到p，也是node左子树的先序子数组，剩下p右边的就是node的右子树的先序子数组

把四个数组找出来，分左右递归调用即可

*/

class Solution {

public:

struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {

int in_size = in.size();

if(in_size == 0)

return NULL;

vector<int> pre_left, pre_right, in_left, in_right;

int val = pre[0];

TreeNode* node = new TreeNode(val);//root node is the first element in pre

int p = 0;

for(p; p < in_size; ++p){

if(in[p] == val) //Find the root position in in

break;

}

for(int i = 0; i < in_size; ++i){

if(i < p){

in_left.push_back(in[i]);//Construct the left pre and in

pre_left.push_back(pre[i+1]);

}

else if(i > p){

in_right.push_back(in[i]);//Construct the right pre and in

pre_right.push_back(pre[i]);

}

}

node->left = reConstructBinaryTree(pre_left, in_left);

node->right = reConstructBinaryTree(pre_right, in_right);

return node;

}

};

```

1. 首先根据根节点a将中序遍历划分为两部分，左边为左子树，右边为右子树
2. 在左子树中根据第一条规则递归，得出左子树
3. 在右子树中根据第一条规则递归，得出右子树
4. 最后合成一棵树
``````function reConstructBinaryTree(pre, vin){
var tree = getTree(pre, vin);//递归调用左子树
return tree;
}

function getTree(pre, vin) {
if(!pre || pre.length === 0) {
return pre;
}
else if(pre.length === 1) {
var lastTree = new TreeNode(pre[0]);
return lastTree;
}
else {
var rootValue = pre[0];//根节点值
var rootIndex = vin.indexOf(rootValue);//根节点在中序遍历中的位置
var tree = new TreeNode(rootValue);
var leftChildVin = vin.slice(0, rootIndex);//左子树的中序遍历
var leftChildPre = pre.slice(1, leftChildVin.length + 1);//左子树的先序遍历
var leftTree = getTree(leftChildPre, leftChildVin);//递归左子树
if(leftTree.val) {
tree.left = leftTree;
}

var rightChildPre = pre.slice(rootIndex + 1);//右子树的先序遍历
var rightChildVin = vin.slice(rootIndex + 1);//右子树的中序遍历
var rightTree = getTree(rightChildPre, rightChildVin);//递归右子树
if(rightTree.val) {
tree.right = rightTree;
}
return tree;
}
}
``````

``````class Solution {
public:
vector<int> my_copy(vector<int> a, int left, int right){
return vector<int> (a.begin()+left, a.begin()+right);
}

TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.size() == 0 || vin.size() == 0) return NULL;
TreeNode *node = new TreeNode(pre[0]);
for(int i = 0; i < vin.size(); i++){
if(pre[0] == vin[i]){
node->left = reConstructBinaryTree(my_copy(pre, 1, i+1),
my_copy(vin, 0, i));
node->right = reConstructBinaryTree(my_copy(pre, i+1, pre.size()),
my_copy(vin, i+1, vin.size()));
}
}
return node;
}
};
``````

```class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
if len(tin) == 0:
return None
else:
root = TreeNode(pre[0])
slt = tin.index(pre[0])
root.left = self.reConstructBinaryTree(pre[1:1+slt],tin[:slt])
root.right = self.reConstructBinaryTree(pre[1+slt:],tin[slt+1:])
return root
```

/*
* 写递归需要注意一个前提和三个要点：
* 前提：
*   通过逻辑分析，发现问题可以用递归实现，一般如果发现有相似的循环逻辑即很可能可以用递归实现，当然这得靠对递归有
* 要点1：
*   起始条件——递归调用以什么样的起始条件开始，而这个起始条件又具有复用性，实际起始条件就是逻辑分析中的“输入”条件。
* 要点2：
*   n——>n+1的转换——即实际的迭代函数体
* 要点3：
*   结束条件——通常迭代过程并不会产生最后的结果，只有跳出的时候才开始发挥迭代过程中做的工作，所以需要计算好跳出的条件
*
* */

```public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
return rebuildTree(pre, in, 0, pre.length-1, 0, in.length-1);
}
private TreeNode rebuildTree(int[] pre, int[] in, int pre_start, int pre_end, int in_start, int in_end){
if(pre_start>pre_end)
return null;
int pre_root = pre[pre_start];
int in_root_index = 0;
while(in_root_index <= in_end){
if(in[in_root_index] == pre_root){
break;
}
in_root_index++;
}
int length = in_root_index - in_start;
TreeNode treeNode = new TreeNode(pre_root);
/*42-51即实际迭代的函数体：求出当前root节点在前序中序额位置，然后分开，再由下式进行第n此迭代*/
treeNode.left = rebuildTree(pre, in, pre_start+1, pre_start+length, in_start, in_root_index-1);
treeNode.right = rebuildTree(pre, in, pre_start+length+1, pre_end, in_root_index+1, in_end);
return treeNode;
}

```

1645条回答 158535浏览

# 通过挑战的用户

• 2019-05-24 17:55:44
• 2019-05-24 17:55:01
• 2019-05-24 17:54:59
• 2019-05-24 17:50:38
• 2019-05-24 17:44:53

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题