给出一棵树的前序遍历和中序遍历，请构造这颗二叉树
注意：
可以假设树中不存在重复的节点
[编程题]从前序和中序遍历构造二叉树
class Solution {
public:
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
return build(preorder,inorder,0,preorder.size()-1,0,preorder.size()-1);
}
TreeNode *build(vector<int> &preorder,vector<int> &inorder,int l1,int r1,int l2,int r2)
{
if(l1 > r1)
return NULL;
int i,count=0,R = preorder[l1];
for(i=l2;i<=r2 && inorder[i]!=R;i++)
count++;
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->val = R;
root->left = build(preorder,inorder,l1+1,l1+count,l2,i-1);
root->right = build(preorder,inorder,l1+1+count,r1,i+1,r2);
return root;
}
};
发表于 2017-08-14 01:05:12
回复(0)
更多回答
/*
* 假设树的先序遍历是12453687，中序遍历是42516837。
* 这里最重要的一点就是先序遍历可以提供根的所在，
* 而根据中序遍历的性质知道根的所在就可以将序列分为左右子树。
* 比如上述例子，我们知道1是根，所以根据中序遍历的结果425是左子树，而6837就是右子树。
* 接下来根据切出来的左右子树的长度又可以在先序便利中确定左右子树对应的子序列
* （先序遍历也是先左子树后右子树）。
* 根据这个流程，左子树的先序遍历和中序遍历分别是245和425，
* 右子树的先序遍历和中序遍历则是3687和6837，我们重复以上方法，可以继续找到根和左右子树，
* 直到剩下一个元素。
*/
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
private TreeNode buildTree(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {
if(preRight<preLeft)
return null;
TreeNode node=new TreeNode(preorder[preLeft]);
if(preRight==preLeft)
return node;
int num=0;
for(int i=inLeft;i<=inRight;i++){
if(inorder[i]==preorder[preLeft]){
num=i;
break;
}
}
int length=num-inLeft;
node.left=buildTree(preorder,preLeft+1,preLeft+length,inorder,inLeft,inLeft+length-1);
node.right=buildTree(preorder,preLeft+length+1,preRight,inorder,num+1,inRight);
return node;
}
发表于 2017-08-06 13:00:49
回复(0)
/*经在leetcode上测试，借助hashmap可以提高不少效率，修改如下*/
import java.util.*;
public class Solution {
HashMap<Integer,Integer> in_map = new HashMap<Integer,Integer>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i <preorder.length; i++)
in_map.put(inorder[i],i);//借助hashmap存储元素在中序遍历中的下标
return helper(0, 0, inorder.length - 1, preorder, inorder);
}
public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart > preorder.length - 1 || inStart > inEnd) return null;
TreeNode root = new TreeNode(preorder[preStart]);
int inIndex = in_map.get(root.val); // 获取该根结点在中序遍历中的下标
root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
return root;
}
}
编辑于 2017-04-02 02:01:19
回复(1)
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int prelen=preorder.length;
int inlen=inorder.length;
return BT(preorder,0,prelen-1,inorder,0,inlen-1);
}
TreeNode BT(int[] preorder,int prestart,int preend,int[] inorder,int instart,int inend)
{
if(instart>inend)
return null;
TreeNode root=new TreeNode(preorder[prestart]);
int mid=0;
for(mid=instart;mid<=inend;mid++)
if(inorder[mid]==root.val)
break;
int leftlen=mid-instart;
root.left=BT(preorder,prestart+1,prestart+leftlen,inorder,instart,mid-1);
root.right=BT(preorder,prestart+leftlen+1,preend,inorder,mid+1,inend);
return root;
}
}
发表于 2019-12-27 13:34:59
回复(0)
/*
* 目的：前+中->二叉树
* 思路：1.首先根据前序遍历获得根节点
* 2.在中序遍历中寻找根节点，进而得到左右子树的中序遍历
* 3.根据左右子树中序遍历的数量，确定左右子树的前序遍历
* 4.递归左右子树求解
*/
TreeNode*getres(vector<int>&preorder,int prestart, int preend, vector<int>&inorder, int instart, int inend){
if (prestart>preend|| instart>inend)
return nullptr;
int pos = instart;
for (;pos<=inend;++pos){
if (preorder[prestart]== inorder[pos]){
break;
}
}
TreeNode*root = new TreeNode(preorder[prestart]);
int len = pos-instart;
root->left = getres(preorder, prestart+1,prestart+len,inorder, instart, pos-1);
root->right = getres(preorder, prestart+len+1, preend,inorder, pos+1,inend);
return root;
}
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
int len = preorder.size();
return getres(preorder,0, len-1 ,inorder,0, len-1);
}
发表于 2019-12-07 14:43:08
回复(0)
//C++迭代器
class Solution {
void buildTree(TreeNode*& root, vector<int>::iterator pre_begin, vector<int>::iterator pre_end, vector<int>::iterator in_begin, vector<int>::iterator in_end)
{
if (pre_begin == pre_end) {
root = nullptr;
return;
}
root = new TreeNode(*pre_begin);
auto it = find(in_begin, in_end, *pre_begin);
buildTree(root->left, pre_begin + 1, pre_begin + 1 + (it - in_begin), in_begin, it);
buildTree(root->right, pre_begin + (it - in_begin) + 1, pre_end, it + 1, in_end);
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
{
TreeNode* root;
buildTree(root, preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
return root;
}
};
编辑于 2019-05-11 11:40:16
回复(0)
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return helper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
public TreeNode helper(int[] preorder, int[] inorder, int preBegin, int preEnd, int inBegin, int inEnd){
if(preBegin > preEnd) return null;
int value = preorder[preBegin];
TreeNode root = new TreeNode(value);
int preMid = preBegin + 1, inMid = inBegin;
for(int i = inBegin; i <= inEnd; i++){
if(inorder[i] == value) break;
preMid++; inMid++;
}
root.left = helper(preorder, inorder, preBegin + 1, preMid - 1, inBegin, inMid - 1);
root.right = helper(preorder, inorder, preMid, preEnd, inMid + 1, inEnd);
return root;
}
}
发表于 2019-10-26 10:42:22
回复(0)
/*
递归求解。
先序遍历的第一个节点为当前根节点。
中序遍历该数的左边序列为当前节点左子树的中序遍历序列。
右边序列为右子数的中序遍历序列。
*/
public class Solution {
private int[] preorder;
private int[] inorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
this.inorder = inorder;
return decideNode(0, 0, inorder.length - 1);
}
public TreeNode decideNode(int loc, int beg, int end) {
if (beg > end)
return null;
int mid = 0;
int cnt = 0; //左子树的长度。
for (int i = beg; i <= end; i++) {
cnt++;
if (preorder[loc] == inorder[i]) {
mid = i;
break;
}
}
TreeNode node = new TreeNode(preorder[loc]);
node.left = decideNode(loc + 1, beg, mid - 1);
node.right = decideNode(loc + cnt, mid + 1, end);
return node;
}
}
发表于 2019-06-19 09:30:48
回复(0)
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// Construct Binary Tree from Preorder and Inorder Traversal
TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> in) {
return constructBiTree(pre, 0, pre.size() - 1, in, 0, in.size() - 1);
}
TreeNode* constructBiTree(vector<int> pre, int preStart, int preEnd, vector<int> in, int inStart, int inEnd) {
// 递归终结条件
if(preStart > preEnd || inStart > inEnd) return nullptr;
int value = pre[preStart];
int index;
// 在中序序列中查找根节点
if((index = searchNode(in, value)) == in.size()) return nullptr;
// 构造根节点
TreeNode *root = new TreeNode(value);
int len = index - inStart; // 记录左子树长度
// 递归地构造左右子树
root->left = constructBiTree(pre, preStart + 1, preStart + len, in, inStart, index - 1);
root->right = constructBiTree(pre, preStart + len + 1, preEnd, in, index + 1, inEnd);
return root;
}
// 在中序序列中查找根节点
int searchNode(vector<int> in, int e) {
int i;
for(i = 0; i < in.size(); i++)
if(in[i] == e)
break;
return i;
}
编辑于 2018-03-06 15:12:04
回复(0)
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.Arrays;
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length!=postorder.length){
return null;
}
if(inorder.length==0){
return null;
}
TreeNode root=new TreeNode(inorder[ 0 ]);
if(inorder.length==1){
return root;
}
int index=0;
for(int i=0;i<inorder.length;i++){
if(postorder[i]==inorder[ 0 ]) {
index=i;
break;
}
}
root.left=buildTree(Arrays.copyOfRange(inorder,1,index+1),Arrays.copyOfRange(postorder,0,index));
root.right=buildTree( Arrays.copyOfRange(inorder, index+1,inorder.length) , Arrays.copyOfRange(postorder, index+1,inorder.length) );
return root;
}
}
发表于 2017-08-20 20:46:15
回复(0)
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return f(preorder,0,preorder.length,inorder,0,preorder.length);
}
public TreeNode f(int[] pre,int s,int e,int []mid,int s1,int e1){
if(s==e) return null;
TreeNode t = new TreeNode(pre[s]);
int i=s1;
for(;i<e1;i++)
if(mid[i]==pre[s]) break;
t.left=f(pre,s+1,s+i-s1+1,mid,s1,i);
t.right=f(pre,s+i-s1+1,e,mid,i+1,e1);
return t;
}
}
发表于 2017-07-27 11:02:05
回复(0)
TreeNode *dfs(vector<int> &preorder,int preStart,int preEnd,vector<int> &inorder,int inStart,int inEnd)
{
if(preStart > preEnd)
return nullptr;
TreeNode *root = new TreeNode(preorder[preStart]);
int middle;
for(middle=inStart;middle<=inEnd;middle++)
if(inorder[middle] == root->val)
break;
int leftLen = middle-inStart;
root->left = dfs(preorder,preStart+1,preStart+leftLen,inorder,inStart,middle-1);
root->right = dfs(preorder,preStart+leftLen+1,preEnd,inorder,middle+1,inEnd);
return root;
}
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
{
int pre = preorder.size(),in = inorder.size();
if(pre==0 || in==0 || pre != in)
return nullptr;
return dfs(preorder,0,pre-1,inorder,0,in-1);
}
发表于 2017-07-13 17:04:14
回复(0)
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(inorder==null || preorder==null ||
inorder.length!=preorder.length)
return null;
return
buildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
public TreeNode buildTree(int[] preorder,int start1,int
end1, int[] inorder,int start2,int end2){
if (start1>end1 ||start2>end2)return null;
TreeNode root=new TreeNode(preorder[start1]);
int index=0;
for (int i:inorder){
if (i==preorder[start1]){
break;
}
index++;
}
root.left=buildTree(preorder,start1+1,start1+index-start2,inorder,start2,index-1);
root.right=buildTree(preorder,start1+index-start2+1,end1,inorder,index+1,end2);
return root;
}
发表于 2017-03-24 17:15:43
回复(0)
class Solution {
public:
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
return build(preorder,inorder,0,preorder.size()-1,0,preorder.size()-1);
}
TreeNode *build(vector<int> &preorder, vector<int> &inorder,int l1,int r1,int l2,int r2)
{
if(l1>r1)
return NULL;
int gen=preorder[l1],i,cnt=0;
for(i=l2;i<=r2&&inorder[i]!=gen;cnt++,i++);
TreeNode *root=(TreeNode *)malloc(sizeof(TreeNode));
root->val=gen;
root->left=build(preorder,inorder,l1+1,l1+cnt,l2,i-1);
root->right=build(preorder,inorder,l1+1+cnt,r1,i+1,r2);
return root;
}
};
发表于 2016-08-13 13:03:59
回复(0)
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
function<TreeNode*(int, int, int)> build = [&](int i, int j, int n) -> TreeNode* {
if (n <= 0) return (TreeNode*) nullptr;
auto root = new TreeNode(preorder[i]);
if (n == 1) return root;
int k = j;
while (inorder[k] != preorder[i]) ++k;
int l = k - j;
root->left = build(i + 1, j, l);
root->right = build(i + 1 + l, k + 1, n - 1 - l);
return root;
};
return build(0, 0, preorder.size());
}
};
发表于 2021-09-20 13:58:42
回复(0)
class Solution: def buildTree(self , preorder , inorder ): # write code here node = None if preorder: node = TreeNode(preorder[0]) index = inorder.index(preorder[0]) node.left = self.buildTree(preorder[1:1 + index], inorder[:index]) node.right = self.buildTree(preorder[index + 1:], inorder[index + 1:]) return node
发表于 2021-03-26 11:10:25
回复(0)
采用先序遍历的思想构建即可。
编码过程中，遇到了一个bug，只能通过25%的样例，反复检查逻辑问题，没有什么差错，最后面发现，原来是把第36行的==写成了=2333。总结：定位bug需要从多方面考虑：
- 如果是样例通过不了：考虑算法思路是否有误、运算符是不是写错了
- 如果是编译错误：考虑语法问题
- 如果是段错误、溢出：考虑边界问题，尤其是指针和数组下标
//
// Created by jt on 2020/8/21.
//
#include <vector>
using namespace std;
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int val): val(val), left(0), right(0) {}
};
class Solution {
public:
/**
*
* @param preorder int整型vector
* @param inorder int整型vector
* @return TreeNode类
*/
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
// write code here
int size = preorder.size();
return inOrder(preorder, 0, size - 1, inorder, 0, size -1);
}
TreeNode* inOrder(vector<int> &preorder, int pL, int pR,
vector<int> &inorder, int iL, int iR) {
if (pL > pR) return nullptr;
TreeNode *root = new TreeNode(preorder[pL]);
int mid = iL;
for (; mid <= iR; ++mid)
if (inorder[mid] == root->val) break;
int sizeLeft = mid - iL;
// 中左右 左中右
root->left = inOrder(preorder, pL+1, pL+sizeLeft, inorder, iL, mid-1);
root->right = inOrder(preorder, pL+sizeLeft+1, pR, inorder, mid+1, iR);
return root;
}
};
发表于 2020-08-22 00:57:45
回复(0)
根据前序遍历确定根节点，补一个python解法
class Solution: def buildTree(self , preorder , inorder ): # write code here if not inorder&nbs***bsp;not preorder: return None root = TreeNode(preorder.pop(0)) index = inorder.index(root.val) root.left = self.buildTree(preorder, inorder[:index]) root.right = self.buildTree(preorder, inorder[index+1:]) return root
发表于 2020-06-01 18:32:58
回复(0)
/**
总结
前序和中序的规律是
同为长为n的序列
长为k的左子树 根 长为n-k-1的右子树
根 长为k的左子树 长为n-k-1的右子树
1、确定两个序列中根所在的位置后
2、截出两个左子树序列，继续找左子树的根，将其作为上一根节点的左节点
2、截出两个右子树序列，继续找右子树的根，将其作为上一根节点的右节点
3、递归找根，直到子树为空时结束
**/
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder==null||inorder==null){
return null;
}
return travel(preorder,inorder,0 ,preorder.length-1 , 0,inorder.length-1);
}
public TreeNode travel(int[] preorder, int[] inorder ,int prex , int prey, int inx,int iny ){
if(prex>prey || inx>iny){
return null;
}
TreeNode node = new TreeNode(preorder[prex]);
for (int k = 0 ; inx+k<=iny ; k++){
//注：最好用0，若用inx作为起始，需要减去inx得到相对长度来截取后序遍历。
if(inorder[inx+k]==preorder[prex]){
node.left = travel(preorder,inorder,prex+1 , prex+ k+1 , inx,inx+ k-1);
node.right = travel(preorder,inorder,prex+ k+1 , prey , inx+ k+1,iny);
}
}
return node;
}
}
发表于 2020-04-25 23:20:26
回复(0)
问题信息
难度：
70条回答
66收藏
22631浏览
通过挑战的用户
查看代码-
2022-11-27 11:35:19 -
2022-10-23 00:03:05 -
2022-09-06 14:47:33
-
2022-09-04 10:19:12
-
2022-09-01 12:27:44
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
