首页 > 试题广场 >

从中序和后序遍历构造二叉树

[编程题]从中序和后序遍历构造二叉树
  • 热度指数：16944 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给出一棵树的中序遍历和后序遍历，请构造这颗二叉树
注意：
保证给出的树中不存在重复的节点
示例1

输入

[2,1,3],[2,3,1]

输出

{1,2,3}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
LinuX18头像 LinuX18 
class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) 
    {
       int inLen = inorder.size(),postLen = postorder.size();
       return dfs(inorder,0,inLen-1,postorder,0,postLen-1);
    }
    TreeNode * dfs(vector<int> &inorder,int inStart,int inEnd,vector<int> &postorder,int postStart,int postEnd)
    {
        if(inStart > inEnd)
            return nullptr;
        TreeNode *root = new TreeNode(postorder[postEnd]);
        int middle;
        for(middle=inStart;middle<=inEnd;++middle)
            if(inorder[middle] == root->val)
                break;
        int leftLen = middle-inStart;
        root->left = dfs(inorder,inStart,middle-1,postorder,postStart,postStart+leftLen-1);
        root->right = dfs(inorder,middle+1,inEnd,postorder,postStart+leftLen,postEnd-1);
        return root;
    }
};

发表于 2017-07-13 17:17:13 回复(5)
HW柯可头像 HW柯可 
/*思路：后序遍历（左节点→右节点→根节点）最后一个节点为根节点，因此可以直接确定数组postorder[]最后一个元素是根节点，
然后通过寻找中序遍历（左节点→根节点→右节点）中的根节点即可确定左右子树（根节点前面序列是左子树，根节点后面序列是右子树）
，然后利用递归即可得解*/
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder==null||postorder==null||inorder.length==0||postorder.length==0||postorder.length!=inorder.length){
            return null;
        }
        int in=inorder.length-1;
        int post=postorder.length-1;
        return solve(inorder,0,in,postorder,0,post);
    }
    //x，y分别代表中序遍历起始、结束位置，i,j分别代表后序遍历起始、结束位置
    public TreeNode solve(int[] inorder,int x,int y,int[] postorder,int i,int j){
        if(x>y||i>j){
            return null;
        }
        TreeNode root=new TreeNode(postorder[j]);
            for(int k=x;k<=y;k++){
                if(inorder[k]==postorder[j]){
                    //k-x代表中序遍历中根节点的左子树长度
                    root.left=solve(inorder,x,k-1,postorder,i,i+k-x-1);
                    root.right=solve(inorder,k+1,y,postorder,i+k-x,j-1);
                    break;
                }    
            }    
        return root;
    }
}

编辑于 2020-04-20 11:36:47 回复(0)
啦穷开心~头像 啦穷开心~ 
//不需要辅助函数，简单易懂
//后序遍历容器的最后一个数是根节点，中序遍历的根节点左边是左子树，右边是右子树，
//后序遍历左子树节点值相邻，右子树节点值也相邻。由后序遍历最后一个值将中序遍历分成
//左右两部分，再由这两部分的size将后序遍历分成左右两部分，递归即可

class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        if(inorder.empty())
            return NULL;
        int nodeval=postorder[postorder.size()-1];
        TreeNode* head=new TreeNode(nodeval);
        vector<int>::iterator iter=find(inorder.begin(),inorder.end(),nodeval);
        vector<int>leftin=vector<int>(inorder.begin(),iter);
        vector<int>rightin=vector<int>(iter+1,inorder.end());
        int left=leftin.size();
        int right=rightin.size();
        if(left>0)
        {
            vector<int>leftpo=vector<int>(postorder.begin(),postorder.begin()+left);
            head->left=buildTree(leftin,leftpo);
        }
        if(right>0)
        {
            vector<int>rightpo=vector<int>(postorder.begin()+left,postorder.begin()+left+right);
            head->right=buildTree(rightin,rightpo);
        }
        return head;
    }
};

发表于 2018-07-17 14:58:56 回复(2)
UESTCODER头像 UESTCODER 
class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        vector<int>::size_type lenIn = inorder.size();
        vector<int>::size_type lenPost = postorder.size();
        return buildTree_Aux(inorder,0,lenIn-1,postorder,0,lenPost-1);
    }
    
    TreeNode *buildTree_Aux(vector<int> &inorder,int inB,int inE, 
                            vector<int> &postorder,int poB,int poE) {
        if(inB > inE || poB > poE)
            return NULL;
        //在后序遍历中确定根节点
        TreeNode* root = new TreeNode(postorder[poE]);
        //在中序遍历中确定左右子树
        vector<int>::iterator iter = find(inorder.begin()+inB,inorder.begin()+inE,postorder[poE]);
        int index = iter - inorder.begin();
        root->left = buildTree_Aux(inorder,inB,index-1,postorder,poB,poB+index-1-inB);
        root->right = buildTree_Aux(inorder,index+1,inE,postorder,poB+index-inB,poE-1);
        return root;
    }
};

发表于 2016-09-01 16:41:11 回复(0)
六丶六头像 六丶六 
public class Solution {
    private Map<Integer, Integer> indexForInOrders = new HashMap<>();
    public TreeNode buildTree (int[] inorder, int[] postorder) {
        for(int i = 0; i < inorder.length; i++)
        {
            indexForInOrders.put(inorder[i],i);
        }
        return Rebuid(postorder, 0, postorder.length - 1, 0);
    }
    public TreeNode Rebuid(int[] pos, int posL, int posR, int inL)
    {
        if(posL > posR) return null;
        TreeNode root = new TreeNode(pos[posR]);
        int index = indexForInOrders.get(root.val);
        int leftTreeSize = index - inL;
        root.left = Rebuid(pos, posL, posL + leftTreeSize - 1, inL);
        root.right = Rebuid(pos, posL + leftTreeSize, posR - 1 , inL + leftTreeSize + 1);
        return root;
    }
}

发表于 2020-09-13 12:14:45 回复(0)
C/C++
努力的牛牛头像 努力的牛牛 
    /*
    * 目的：中+后->二叉树
    * 思路：1.由后序遍历确定根节点。
    *      2.在中序遍历中寻找根节点，然后将中序遍历分成左子树的中序遍历和右子树的中序遍历两部分。
    *      3.根据左右子树中序遍历的数量，确定左右子树的后序遍历。
    *      4.递归左右子树。
    */
    TreeNode*getres(vector<int> &inorder, int ins, int ine, vector<int> &postorder, int posts,int poste){
        if (ine-ins<0 || poste-posts<0)
            return nullptr;
        int pos = ins;
        for(;pos<=ine;++pos){
            if (inorder[pos]==postorder[poste])
                break;
        }
        TreeNode*root = new TreeNode(postorder[poste]);
        int len = pos-ins-1;
        root->left = getres(inorder,ins,ins+len,postorder,posts,posts+len);
        root->right = getres(inorder,ins+len+2,ine, postorder,posts+len+1, poste-1);
        return root;
    }
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        return getres(inorder,0,inorder.size()-1, postorder,0,postorder.size()-1);
    }
发表于 2019-12-07 14:37:53 回复(0)
张佃鹏头像 张佃鹏 
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return helper(inorder, postorder, 0, postorder.length - 1, 0, postorder.length - 1);
    }
    
    public TreeNode helper(int[] inorder, int[] postorder, int begin, int end, int postBegin, int postEnd){
        if(begin > end) return null;
        int value = postorder[postEnd];
        TreeNode root = new TreeNode(value);
        int mid = begin, postMid = postBegin;
        for(int i = begin; i <= end; i++){
            if(inorder[i] == value) break;
            mid++;
            postMid++;
        }
        root.left = helper(inorder, postorder, begin, mid - 1, postBegin, postMid - 1);
        root.right = helper(inorder, postorder, mid + 1, end, postMid, postEnd - 1);
        return root;
    }
}

发表于 2019-10-26 10:28:38 回复(0)
tuweilong头像 tuweilong 
/*
与先序，中序思路一样。
唯一不同的是，确定后序中左子树根节点，和右子树根节点比较麻烦。
*/
public class Solution {

    private int[] inorder;
    private int[] postorder;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.inorder = inorder;
        this.postorder = postorder;
        return decideNode(postorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode decideNode(int loc, int beg, int end) {
        if (beg > end) return null;
        int cnt = 0;      //左子树的节点数。
        int mid = 0;
        for (int i = beg; i <= end; i++) {
            if (postorder[loc] == inorder[i]) {
                mid = i;
                break;
            }
            cnt++;
        }
        TreeNode node = new TreeNode(postorder[loc]);
        node.left = decideNode(loc - (end - beg + 1 - cnt), beg, mid - 1);     //数量和坐标之间差1。
        node.right = decideNode(loc - 1, mid + 1, end);
        return node;
    }
}

发表于 2019-06-19 15:42:45 回复(0)
mkckr头像 mkckr 
//C++迭代器
class Solution {
    TreeNode* buildTree(vector<int>::iterator in_begin, vector<int>::iterator in_end, vector<int>::iterator post_begin, vector<int>::iterator post_end)
    {
        if (in_begin == in_end) {
            return nullptr;
        }
        TreeNode* root = new TreeNode(*(post_end - 1));
        auto it = find(in_begin, in_end, *(post_end - 1));
        root->left = buildTree(in_begin, it, post_begin, post_begin + (it - in_begin));
        root->right = buildTree(it + 1, in_end, post_begin + (it - in_begin), post_end - 1);
        return root;
    }

public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
    {
        return buildTree(inorder.begin(), inorder.end(), postorder.begin(), postorder.end());
    }
};
发表于 2019-05-11 11:42:48 回复(0)
LeBronWitness头像 LeBronWitness
二叉树后序遍历的最后一个节点是根节点，从而可以在中序遍历中找到左子树和右子树 
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return dfs(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
    }
    
    public TreeNode dfs(int[] inorder,int x,int y,int[] postorder,int i,int j) {
        if(x>y||i>j) return null;
        TreeNode root = new TreeNode(postorder[j]);
        for(int cnt=x;cnt<=y;cnt++) {
            if(inorder[cnt]==root.val) {
                root.left = dfs(inorder,x,cnt-1,postorder,i,i+cnt-x-1);
                root.right = dfs(inorder,cnt+1,y,postorder,i+cnt-x,j-1);
            }
        }
        return root;
    }
}

发表于 2019-04-30 14:45:51 回复(0)
Java
yqwdxntr头像 yqwdxntr
思路：先通过后序遍历找到根节点，再利用中序遍历将序列划分为左右子树。假设树的后序遍历为342651，树的中序遍历为324165，由后序遍历可知，1为根，由中序遍历可知，324为左子树，65为右子树。然后对左右子树重复以上方法，继续找出子树的根和左右子树。
public TreeNode buildTree(int[] inorder, int[] postorder) {
        TreeNode node=help(inorder, 0, inorder.length-1, postorder,0, postorder.length-1);
        return node;
    }
    public TreeNode help(int[] inorder,int inleft,int inright,int[] postorder, int postleft,int postright){
        if(postleft>postright){
            return null;
        }
        TreeNode node=new TreeNode(postorder[postright]);
        if(postleft==postright){
            return node;
        }
        int num=0;
        for(int i=inleft;i<=inright;i++){
            if(postorder[postright]==inorder[i]){
                num=i;
                break;
            }
        }
        int length=num-inleft;
        
        node.left=help(inorder, inleft,num-1,postorder,postleft,postleft+length-1);
        node.right=help(inorder, num+1,inright,postorder,postleft+length,postright-1);
        
        return node;
    }

发表于 2018-11-20 15:25:57 回复(0)
顾翅头像 顾翅 
class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        return build(inorder,postorder,0,inorder.size()-1,0,postorder.size()-1);
    }
    TreeNode* build(vector<int> &inorder, vector<int> &postorder,int inbegin,int inend,int posbegin,int posend){
        if(inbegin>inend||posbegin>posend)
            return NULL;
        TreeNode* root=new TreeNode(postorder[posend]);
        for(int i=inbegin;i<=inend;i++){
            if(inorder[i]==postorder[posend]){
                root->left=build(inorder,postorder,inbegin,i-1,posbegin,posbegin+i-1-inbegin);
                root->right=build(inorder,postorder,i+1,inend,posend-inend+i,posend-1);
            }
        }
        return root;
    }
};
发表于 2018-05-30 20:38:36 回复(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:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        return create(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);
    }
    TreeNode* create(vector<int> &inorder, vector<int> &postorder, int is, int ie, int ps, int pe){
        if(ps>pe) return NULL;
        TreeNode* root = new TreeNode(postorder[pe]);
        int mid;
        for (int i=is; i<=ie;i++){
            if (root->val==inorder[i]){
                mid = i;
                break;
            }
        }
        root->left = create(inorder, postorder, is, mid-1, ps, ps+mid-is-1);
        root->right = create(inorder, postorder, mid+1, ie, pe - ie + mid, pe - 1);
        return root;
    }
};

发表于 2017-12-12 00:19:05 回复(0)
C/C++
Ga_li_dun_farming_guy头像 Ga_li_dun_farming_guy 
//root->left卡了好久。才想通，有点小纠结。
class Solution {
public:
    TreeNode* func(vector<int> &in, vector<int> &pos, int start, int end, int head)
    {
        if(start >= end || head < 0) return NULL;
        int mid = start;
        for(;mid < end;mid++) 
            if(in[mid] == pos [head]) 
                break;
        if(mid >= end) return NULL;
        TreeNode *root = new TreeNode(pos[head]);
        root->left = func(in,pos,start,mid,head-end + mid);
        root->right= func(in,pos,mid+1,end,head-1);
        return root;
    }
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        if(inorder.size() == 0 || postorder.size() == 0) return NULL;
        return func(inorder,postorder,0,postorder.size(),postorder.size()-1);
    }
};
发表于 2017-11-13 21:39:54 回复(0)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        int l_in = inorder.size(),l_post = postorder.size();
        return DFS(inorder,0,l_in-1,postorder,0,l_post-1);
    }
    TreeNode *DFS(vector<int> &inorder,int in_start,int in_end,vector<int> &postorder,int post_start,int post_end)
    {
    	if(in_start > in_end)
    		return NULL;
    	TreeNode *root = new TreeNode(postorder[post_end]);
    	int mid;
    	for(mid=in_start;mid<=in_end;mid++)
    	{
    		if(inorder[mid] == root->val)
    			break;
		}
		int l_left = mid - in_start;
		root->left = DFS(inorder,in_start,mid-1,postorder,post_start,post_start+l_left-1);
		root->right = DFS(inorder,mid+1,in_end,postorder,post_start+l_left,post_end-1);
		return root;
	}
};


发表于 2017-09-01 02:02:00 回复(0)
Java
阿拉要洗澡头像 阿拉要洗澡
/**
 * 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(postorder[ inorder.length-1 ]);
        
        if(inorder.length==1){
            
            return root;
        }
        
        int index=0;
        
        for(int i=0;i<inorder.length;i++){
            
        if(inorder[i]==postorder[ inorder.length-1 ]) {
                
                index=i;
            break;
                
            }
            
    }
        
    root.left=buildTree(Arrays.copyOfRange(inorder,0,index),Arrays.copyOfRange(postorder,0,index));
    root.right=buildTree( Arrays.copyOfRange(inorder, index+1,inorder.length) , Arrays.copyOfRange(postorder, index,inorder.length-1) );
   
    return root;
    
    }
    
    
}
发表于 2017-08-20 20:39:25 回复(0)
后劲好大头像 后劲好大 
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0)
        	return null;
        
        return helpTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);	
    }
	
	public TreeNode helpTree(int[] inorder, int beginin, int endin, int[] postorder, int beginpos, int endpos){
		if(beginin > endin || beginpos > endpos)
			return null;
		
		// 后序遍历的最后一个元素为root，然后我们找到先序遍历的数组中
                // root所在的位置，root前为左子树，后边为右子树
		TreeNode root = new TreeNode(postorder[endpos]);
		int inx = beginin;
		for(int i = beginin; i <= endin; i++){
			if(inorder[i] == postorder[endpos]){
				inx = i;
				break;
			}
		}
		root.left = helpTree(inorder, beginin, inx - 1, postorder, beginpos, beginpos + inx - beginin - 1);
		root.right = helpTree(inorder, inx + 1, endin, postorder, beginpos + inx - beginin, endpos - 1);
		return root;		
	}
}

发表于 2017-07-02 16:14:16 回复(1)
C/C++
油头教授的坩埚头像 油头教授的坩埚 
class Solution { public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { if(inorder.size() == 0)return NULL;
        TreeNode *p;
        TreeNode *root;
        stack<TreeNode *> stn;
        
        root = new TreeNode(postorder.back()); 
        stn.push(root); 
        postorder.pop_back(); while(true)
        { if(inorder.back() == stn.top()->val) { p = stn.top(); stn.pop(); inorder.pop_back(); if(inorder.size() == 0) break; if(stn.size() && inorder.back() == stn.top()->val) continue; p->left = new TreeNode(postorder.back()); 
                postorder.pop_back();
                stn.push(p->left);
            } else {
                p = new TreeNode(postorder.back());
                postorder.pop_back();
                stn.top()->right = p; 
                stn.push(p); 
            }
        } return root;
    }
};

发表于 2017-03-12 10:54:48 回复(0)
Java
詆調壹點头像 詆調壹點 
public class Solution {
	public TreeNode buildTree(int[] inorder, int[] postorder) {
		return createBinaryTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
	}

	public TreeNode createBinaryTree(int[] inorder, int inLeft, int inRight, int[] postorder, int postLeft, int postRight) {
		if(inLeft > inRight || postLeft > postRight) return null;
		TreeNode root = new TreeNode(postorder[postRight]);
		int len = 0;
		for (int i = inLeft; i <= inRight; i ++) {
			if(inorder[i] == postorder[postRight]) break;
			len ++;
		}
		root.left = createBinaryTree(inorder, inLeft, inLeft + len - 1, postorder, postLeft, postLeft + len - 1);
		root.right = createBinaryTree(inorder, inLeft + len + 1, inRight, postorder, postLeft + len, postRight - 1);
		return root;
	}
}
编辑于 2017-07-22 23:14:02 回复(0)
大大的逗比头像 大大的逗比 
//和先序加中序构建二叉树是一样的，递归过程
public class 二叉树中序和后序遍历重构_106 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder==null||postorder==null||inorder.length==0) {
			return null;
		}
        return ConstructTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
    }

	private TreeNode ConstructTree(int[] inorder, int inStart, int inEnd,
			int[] postorder, int postStart, int postEnd) {
		if (inStart>inEnd||postStart>postEnd) {
			return null;
		}
		
		TreeNode root=new TreeNode(postorder[postEnd]);
		for (int i = 0; i < postorder.length; i++) {
			if (inorder[i]==postorder[postEnd]) {
				root.left=ConstructTree(inorder, inStart, i-1, postorder, postStart, postStart+i-1-inStart);
				root.right=ConstructTree(inorder, i+1, inEnd, postorder, postStart+i-inStart, postEnd-1);
			}
		}
		return root;
	}
}


发表于 2016-08-30 22:24:50 回复(0)
提交观点

问题信息

树 递归
难度：
85条回答 27583浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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