首页 > 试题广场 > 重建二叉树
[编程题]重建二叉树
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

1527个回答

添加回答
推荐
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 回复(197)

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
编辑于 2017-10-13 21:55:21 回复(64)
/**
 * 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;
        //创建根节点,根节点肯定是前序遍历的第一个数
        TreeNode* head=new TreeNode(pre[0]);
        //找到中序遍历根节点所在位置,存放于变量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排序的思想类似,取出前序和中序遍历根节点左边和右边的子树
        //递归,再对其进行上述所有步骤,即再区分子树的左、右子子数,直到叶节点
       head->left=reConstructBinaryTree(left_pre,left_in);
       head->right=reConstructBinaryTree(right_pre,right_in);
       return head;
    }
};


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

发表于 2016-06-23 16:56:14 回复(45)
用js写一个

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 = [];
    
    var head = new TreeNode(pre[0]);
    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]);
    }
    
    head.left = reConstructBinaryTree(left_pre, left_in);
    head.right = reConstructBinaryTree(right_pre, right_in);
    
    return head;
    
}
module.exports = {
    reConstructBinaryTree : reConstructBinaryTree
};

发表于 2017-03-24 14:39:03 回复(4)
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)
        };
}

编辑于 2017-03-30 13:46:35 回复(5)
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

发表于 2016-10-13 22:03:55 回复(6)
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 回复(7)
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;      
    }
}
发表于 2015-10-05 13:37:18 回复(2)
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;
    }
}

发表于 2015-11-25 14:32:29 回复(5)
/* 先序遍历第一个位置肯定是根节点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 回复(9)
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)
			preList.add(i);
		for (int i : in)
			inList.add(i);
		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;
	}
}



发表于 2015-07-15 22:23:16 回复(2)

标准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;
    }
};
发表于 2018-01-23 21:23:31 回复(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 回复(2)
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 回复(4)

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

思路:

  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)
发表于 2017-11-27 23:18:52 回复(4)

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

发表于 2018-05-16 17:49:06 回复(0)
好吧,我承认我从网上借鉴的,虽然懂得逻辑,但不会用递归实现,特来学习一下:

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

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

扫描二维码,关注牛客网公众号

  • 公司地址:北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号