首页 > 试题广场 >

重建二叉树

[编程题]重建二叉树
  • 热度指数:1317322 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定节点数为 n 的二叉树的前序遍历和中序遍历结果,请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出如下图所示。


提示:
1.vin.length == pre.length
2.pre 和 vin 均无重复元素
3.vin出现的元素均出现在 pre里
4.只需要返回根结点,系统会自动输出整颗树做答案对比
数据范围:,节点的值
要求:空间复杂度 ,时间复杂度
示例1

输入

[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]

输出

{1,2,3,4,#,5,6,#,7,#,#,8}

说明

返回根节点,系统会输出整颗二叉树对比结果,重建结果如题面图示    
示例2

输入

[1],[1]

输出

{1}
示例3

输入

[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]

输出

{1,2,5,3,4,6,7}

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
推荐
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;
    }
}

编辑于 2018-03-21 14:58:42 回复(255)
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; 
    }
};


发表于 2015-09-07 17:02:23 回复(10)
/* 先序遍历第一个位置肯定是根节点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;
    }
};

编辑于 2016-02-29 13:48:56 回复(11)
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;
	}
};

发表于 2016-07-13 11:09:02 回复(5)

JavaScript
递归思想

        function reConstructBinaryTree(pre, vin) {
            // write code here
            var head = new TreeNode(pre[0]),
                headIndex = vin.indexOf(pre[0]),
                leftVin = vin.slice(0, headIndex),
                rightVin = vin.slice(headIndex + 1),
                leftPre = pre.slice(1, 1 + leftVin.length),
                rightPre = pre.slice(1 + leftVin.length);
            if(leftPre.length != 0){
                head.left = reConstructBinaryTree(leftPre, leftVin);
            }
            if(rightPre.length !=0 ){
                head.right = reConstructBinaryTree(rightPre, rightVin);
            }
            return head;
        }
发表于 2019-05-07 17:38:04 回复(0)

前序遍历的结果中,第一个结点一定是根结点,然后在中序遍历的结果中查找这个根结点,根结点左边的就是左子树,根结点右边的就是右子树,递归构造出左、右子树即可

发表于 2018-05-16 17:49:06 回复(0)
/* 先序遍历第一个位置肯定是根节点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;
    }
};

编辑于 2016-02-29 13:49:43 回复(3)
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) {
 
 }
}

编辑于 2015-04-10 11:30:36 回复(0)

先序遍历特点:第一个值是根节点
中序遍历特点:根节点左边都是左子树,右边都是右子树

思路:

  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;
        }
}
发表于 2018-04-06 20:54:55 回复(0)
/**
 * 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;
    }
}

发表于 2021-09-27 08:41:17 回复(0)
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)划分左子树右子树
问题自然迎刃而解
发表于 2018-01-15 20:30:37 回复(1)
好吧,我承认我从网上借鉴的,虽然懂得逻辑,但不会用递归实现,特来学习一下:

  /*
  * 写递归需要注意一个前提和三个要点:
  * 前提:
  *   通过逻辑分析,发现问题可以用递归实现,一般如果发现有相似的循环逻辑即很可能可以用递归实现,当然这得靠对递归有
  * 要点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;
  }

编辑于 2017-12-25 14:50:12 回复(0)
嘗試盡量用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;
    }
};

发表于 2021-09-23 23:59:32 回复(0)
递归建树,每次确定子树的前序顺序和中序顺序即可
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;
};

发表于 2016-08-18 15:01:17 回复(0)
java  记录刷题的过程
/**
 * 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;
    }
}

发表于 2021-06-05 21:23:27 回复(1)
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))
    };
}

发表于 2021-04-05 12:23:29 回复(0)

参考欲风,进行了详细解释===>

【剑指Offer】4、重建二叉树:https://blog.csdn.net/HeavenDan/article/details/103593405

编辑于 2019-12-19 17:45:53 回复(0)
Python解法:
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


编辑于 2019-12-17 16:59:14 回复(0)
# -*- 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


发表于 2019-03-01 21:05:30 回复(0)

JS 递归写法, 实际上很简单.

  1. 前序的第一个是根节点
  2. 在中序中找到该节点, 则左边的为该根节点左子树, 右边为右子树.
  3. 递归构建子树.
    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
    }
发表于 2019-01-17 03:50:33 回复(0)
思路:就是递归后让其仍然是和原来给的状态一样的,一个先序的和一个后序的
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;  
    }  
}

发表于 2018-03-26 12:03:13 回复(0)