[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
{1,2,3,4,#,5,6,#,7,#,#,8}返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示
[1],[1]
{1}[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
{1,2,5,3,4,6,7}
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 preint p = 0;for(p; p < in_size; ++p){if(in[p] == val) //Find the root position in inbreak;}for(int i = 0; i < in_size; ++i){if(i < p){in_left.push_back(in[i]);//Construct the left pre and inpre_left.push_back(pre[i+1]);}else if(i > p){in_right.push_back(in[i]);//Construct the right pre and inpre_right.push_back(pre[i]);}}node->left = reConstructBinaryTree(pre_left, in_left);node->right = reConstructBinaryTree(pre_right, in_right);return node;}};
public class Solution{
//通过传进前序遍历，和中序遍历 重建二叉树（可以输出新建的二叉树的后序遍历）
//递归方法重构树
public static TreeNode reConstructBinaryTree
(int[] pre,int[] in ){
if(pre==null||in==null){
return null;
}
return ConstructCore(pre, in,
0, pre.length-1, 0, in.length-1);
}
//重构二叉树核心代码核心代码
public static TreeNode ConstructCore
(int[] pre,int[] in,
int preStart,int preEnd,int inStart,int inEnd){
//通过前序遍历序列找到根节点，很显然是序列第一个值
//创建根节点
TreeNode root=new TreeNode (pre[preStart]);
root.left=null;
root.right=null;
//当遇到特殊情况
if(preStart==preEnd&&inStart==inEnd){
return root;
}else{
//throw new Exception();
System.err.println("输入错误！");
}
//通过前序遍历序列所得到的根节点在中序遍历根节点的位置
int rootInorder=0;
for(rootInorder=inStart;rootInorder<=inEnd;rootInorder++){
if(in[rootInorder]==pre[preStart])
break;
else if(rootInorder==inEnd){
System.err.println("输入错误");
}
}
//开始分割左右子树
//左子树长度
int leftTreeLength=rootInorder-inStart;
//右子树长度
int rightTreelength=inEnd-rootInorder;
//开始构建左右子树
//构建左子树
if(leftTreeLength>0){
root.left=ConstructCore(pre, in,
preStart+1, preStart+leftTreeLength,
inStart,rootInorder-1);
}
//构建右子树
if(rightTreelength>0){
root.right=ConstructCore(pre, in,
preStart+leftTreeLength+1, preEnd,
rootInorder+1,inEnd);
}
return root;
}
public static void main(String[] args) {
}
}
先序遍历特点：第一个值是根节点
中序遍历特点：根节点左边都是左子树，右边都是右子树
思路：
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;
}
}
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.*;
public class Solution {
// 前序遍历第1个节点必定是子树的根结点
// 根据这个根结点，可以在中序遍历序列中划分左右子树
Map<Integer, Integer> inorderSet = new HashMap<>();
public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
// 使用HashMap记录中序遍历序列的结点值和索引
// 以便后期能够根据前序遍历的根结点，在中序遍历序列中划分左右子树
int index = 0;
for(int root : vin)
inorderSet.put(root, index ++);
return buildTree(pre, 0, pre.length - 1, vin, 0, vin.length - 1);
}
public TreeNode buildTree(int[] pre, int preL, int preR,
int[] inorder, int inL, int inR){
if(preL > preR)
return null;
// 前序遍历第1个结点就是根结点
// 根据这个根结点可以到中序遍历序列中划分左右子树
// 先在中序遍历序列中找到这个根结点的索引
int inOrderRoot = inorderSet.get(pre[preL]);
// 根据中序遍历序列，计算左子树的长度 [左子树] inOrderRoot [右子树]
int subLen = inOrderRoot - inL;
// 建立根结点
TreeNode root = new TreeNode(pre[preL]);
// 创建左子树
// 前序遍历 preL,[preL + 1, preL + subLen]
// 中序遍历 [inL, inOrderRoot - 1]
root.left = buildTree(pre, preL + 1, preL + subLen,
inorder, inL, inOrderRoot - 1);
// 创建右子树
// 前序遍历 preL,[preL + 1, preL + subLen],[preL + subLen + 1, preR]
// 中序遍历 [inL, inOrderRoot - 1], inOrderRoot, [inOrderRoot + 1, inR]
root.right = buildTree(pre, preL + subLen + 1, preR,
inorder, inOrderRoot + 1, inR);
// 最后返回这棵树
return root;
}
} 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
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;
}
嘗試盡量用STL來解，主要用遞歸實現，傳進下一層的子vector使用std::initializer_lists創建。
class Solution {
public:
TreeNode *reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if (pre.empty())
return nullptr;
TreeNode *root = new TreeNode(pre.front());
vector<int>::iterator root_vin = find(vin.begin(), vin.end(), root->val);
int rootIdx_vin = root_vin - vin.begin();
root->left = reConstructBinaryTree({pre.begin() + 1, pre.begin() + rootIdx_vin + 1}, {vin.begin(), root_vin});
root->right = reConstructBinaryTree({pre.begin() + rootIdx_vin + 1, pre.end()}, {root_vin + 1, vin.end()});
return root;
}
}; 
class Solution {
public:
struct TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> in) {
m_pre = pre;
m_in = in;
return reConstruct(0, m_pre.size() - 1, 0, m_in.size()-1);
}
struct TreeNode* reConstruct(int L1, int R1, int L2, int R2){
if (L1>R1)
return nullptr;
int cur_head = m_pre[L1];
TreeNode *head = new TreeNode(cur_head);
int i = L2;
while (m_in[i] != cur_head) ++i;
int left_len = i - L2;
head->left = reConstruct(L1 + 1, L1 + left_len, L2, L2 + left_len - 1);
head->right = reConstruct(L1 + left_len + 1, R1, L2 + left_len + 1, R2);
return head;
}
private:
//代替全局变量
vector<int> m_pre;
vector<int> m_in;
};
/**
* 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;
}
return res(pre,0,pre.length-1,in,0,in.length-1);
}
public static TreeNode res(int[] pre,int preLeft,int preRight,int[] in,int inLeft,int inRight){
if (preLeft>preRight){
return null;
}
TreeNode root = new TreeNode(pre[preLeft]);
int index = 0;
for(int i =inLeft;i<=inRight;i++){
if (in[i]==pre[preLeft]){
index = i;
break;}
}
root.left = res(pre,preLeft+1,preLeft+index-inLeft,in,inLeft,index-1);
root.right = res(pre,preLeft+index-inLeft+1,preRight,in,index+1,inRight);
return root;
}
} 
function reConstructBinaryTree(pre, vin)
{
// write code here
//先找出根节点，然后分割成左子树和右子树，再分别对左右子树递归做同样的操作
if (pre.length === 0 || vin.length === 0) {
return null;
}
var index = vin.indexOf(pre[0]),
left = pre.slice(1,index + 1),
right = pre.slice(index + 1);
return {
val : pre[0],
left : reConstructBinaryTree(left,vin.slice(0,index)),
right : reConstructBinaryTree(right,vin.slice(index + 1))
};
} 参考欲风，进行了详细解释===>
【剑指Offer】4、重建二叉树：https://blog.csdn.net/HeavenDan/article/details/103593405
class Solution: # 返回构造的TreeNode根节点 def reConstructBinaryTree(self, pre, tin): if not pre or not tin: return None root = TreeNode(pre[0]) index = tin.index(root.val) root.left = self.reConstructBinaryTree(pre[1:index+1], tin[:index]) root.right = self.reConstructBinaryTree(pre[index+1:], tin[index+1:]) return root
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # 返回构造的TreeNode根节点 def reConstructBinaryTree(self, pre, tin): # write code here # 思路：前序遍历的首个元素是根节点，在中序遍历中找到该节点，确定左右子树节点个数 # 这时又分别得到左右子树的前中遍历序列，递归处理 # 如果遍历序列为空，则是空树，返回None # 注意输入类型为int类型list，实际str类型处理更简单，因为split可以直接分割 if (len(pre) == 0) & (len(tin) == 0): return None # 对任意子树，根为前序遍历首个元素 x = pre[0] node = TreeNode(x) # 计算左子树个数 left_count = 0 for i in tin: if i==x: break else: left_count = left_count+1 # 根据左子树个数截取前序和中序遍历序列 # [:]如果截取失败自动返回空字符串''，不用判断左右子树是否为空 left_pre = pre[1:1 + left_count] right_pre = pre[1 + left_count:] left_in = tin[0:left_count] right_in = tin[left_count+1:] # 递归处理左右子树 node.left = self.reConstructBinaryTree(left_pre, left_in) node.right = self.reConstructBinaryTree(right_pre, right_in) return node
function reConstructBinaryTree (pre, vin) {
if (pre.length === 0 || vin.length === 0) return null
let root = new TreeNode(pre[0])
let rootIndex = vin.indexOf(root.val)
root.left = reConstructBinaryTree(pre.slice(1, rootIndex + 1), vin.slice(0, rootIndex))
root.right = reConstructBinaryTree(pre.slice(rootIndex + 1), vin.slice(rootIndex + 1))
return root
}
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length==0||in.length==0) return null;
TreeNode root=new TreeNode(pre[0]);//前序的第一个数定为根
int len=pre.length;
//当只有一个数的时候
if(len==1){
root.left=null;
root.right=null;
return root;
}
//找到中序中的根位置
int rootval=root.val;
int i;
for(i=0;i<len;i++){
if(rootval==in[i])
break;
}
//创建左子树
if(i>0){
int[] pr=new int[i];
int[] ino=new int[i];
for(int j=0;j<i;j++){
pr[j]=pre[j+1]; //去掉了已知的根节点，将新的数组成为先序和中序
}
for(int j=0;j<i;j++){
ino[j]=in[j];
}
root.left=reConstructBinaryTree(pr,ino);
}else{
root.left=null;
}
//创建右子树
if(len-i-1>0){
int[] pr=new int[len-i-1];
int[] ino=new int[len-i-1];
for(int j=i+1;j<len;j++){ //去掉了已知的根节点，将新的数组成为先序和中序
ino[j-i-1]=in[j];
pr[j-i-1]=pre[j];
}
root.right=reConstructBinaryTree(pr,ino);
}else{
root.right=null;
}
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:
stack<int> parStk;
stack<TreeNode*> nodeStk;
//定义自己的出栈入栈方法来维护栈。
TreeNode* pop(int* j,int* m,int* n){
TreeNode* temp = nodeStk.top();
nodeStk.pop();
*n = parStk.top();
parStk.pop();
*m = parStk.top();
parStk.pop();
*j = parStk.top();
parStk.pop();
return temp;
}
void push(TreeNode* node,int j,int m,int n){
parStk.push(j);
parStk.push(m);
parStk.push(n);
nodeStk.push(node);
}
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
TreeNode* nodes;
TreeNode* root;
TreeNode* tempRoot;
int size = pre.size();
int i,j,m,n,v;
int leftNum,rightNum;
if(0 == pre.size() || 0 == vin.size()){
return NULL;
}
tempRoot = root = new TreeNode(pre[0]);
j = 0,
m = 0;
n = size - 1;
//栈中保存的始终是当前子树的根节点,
//j为根节点在前序遍历中的下标
//m为当前子树的中序遍历前界
//n为当前子树的中序遍历后界
//初始入栈
push(tempRoot,j,m,n);
while(!parStk.empty()){
tempRoot = pop(&j,&m,&n);
for(v = m;v <= n;++v){
if(vin[v] == tempRoot->val){
break;
}
}
//v是当前子树根节点在中序遍历中的下标
leftNum = v - m;
rightNum = n - v;
//如果左子树节点数不为零，构造左子树的参数入栈，相当于递归调用构造左子树的函数
if(leftNum > 0){
tempRoot->left = new TreeNode(pre[j + 1]);
push(tempRoot->left,j + 1,m,v - 1);
}
//如果右子树节点数不为零，构造右子树的参数入栈，相当于递归调用构造右子树的函数
if(rightNum > 0){
tempRoot->right = new TreeNode(pre[j + leftNum + 1]);
push(tempRoot->right,j + leftNum + 1,v + 1,n);
}
}
return root;
}
};
class Solution {
public:
TreeNode* reConstructBinaryTree(vector pre,vector vin) {
if(pre.size()==0) return NULL;
int root_value = pre[0];
TreeNode* root = new TreeNode(root_value);
vector::iterator s = find(vin.begin(), vin.end(),root_value);
if(s!=pre.begin()) root->left = reConstructBinaryTree(vector(pre.begin()+1,s-vin.begin()+pre.begin()+1),vector(vin.begin(),s));
if(s!=pre.end()) root->right = reConstructBinaryTree(vector(s-vin.begin()+pre.begin()+1,pre.end()),vector(s+1,vin.end()));
return root;
}
};
/* 思路清晰版 */
class Solution{
TreeNode* ReConstructBiTree(vector<int> &pre,vector<int> &vin)
{
int rootValue = pre[0];
TreeNode *pRoot = new TreeNode(rootValue);
// 将中序遍历结果分为左右两部分
vector<int> vinL,vinR,preL,preR;
int i = 0,j = 1;
while(vin[i] != rootValue){
vinL.push_back(vin[i++]);
preL.push_back(pre[j++]);
}
++i;
while(i < vin.size()){
vinR.push_back(vin[i++]);
preR.push_back(pre[j++]);
}
// 构建左右子树
if(!vinL.empty() && !preL.empty())
pRoot->left = ReConstructBiTree(preL,vinL);
if(!vinR.empty() && !preR.empty())
pRoot->right = ReConstructBiTree(preR,vinR);
return pRoot;
}
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin)
{
if(pre.empty() || vin.empty() || pre.size() != vin.size())
return NULL;
return ReConstructBiTree(pre,vin);
}
};
/* 迭代器版本 -- 麻烦 */
class Solution {
private:
TreeNode* ReConstructBiTreeCore(vector<int>::iterator startPre,vector<int>::iterator endPre,
vector<int>::iterator startVin,vector<int>::iterator endVin)
{
int rootValue = *startPre;
TreeNode *root = new TreeNode(rootValue);
// 如果只有一个结点，则返回为根节点
if(startPre == endPre)
if(startVin == endVin && *startPre == *startVin) return root;
// 如果大于一个结点，则中序遍历找到根节点
vector<int>::iterator rootInVin = startVin;
while(rootInVin <= endVin && *rootInVin != rootValue){
++rootInVin;
}
int leftLength = rootInVin - startVin;
vector<int>::iterator leftPreEnd = startPre+leftLength;
// 重构左子树
if(leftLength > 0){
root->left = ReConstructBiTreeCore(startPre+1,leftPreEnd,startVin,rootInVin-1);
}
// 重构右子树
if(leftLength < endPre-startPre){
root->right = ReConstructBiTreeCore(leftPreEnd+1,endPre,rootInVin+1,endVin);
}
return root;
}
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.empty() || vin.empty())
return nullptr;
return ReConstructBiTreeCore(pre.begin(),(pre.begin()+(pre.size()-1)),vin.begin(),(vin.begin()+(vin.size()-1)));
}
};
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
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; } }