给出一棵树的中序遍历和后序遍历，请构造这颗二叉树
注意：
保证给出的树中不存在重复的节点
[编程题]从中序和后序遍历构造二叉树
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)
//不需要辅助函数，简单易懂
//后序遍历容器的最后一个数是根节点，中序遍历的根节点左边是左子树，右边是右子树，
//后序遍历左子树节点值相邻，右子树节点值也相邻。由后序遍历最后一个值将中序遍历分成
//左右两部分，再由这两部分的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)
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)
/*
* 目的：中+后->二叉树
* 思路：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)
/*
与先序，中序思路一样。
唯一不同的是，确定后序中左子树根节点，和右子树根节点比较麻烦。
*/
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)
//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)
二叉树后序遍历的最后一个节点是根节点，从而可以在中序遍历中找到左子树和右子树
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)
思路：先通过后序遍历找到根节点，再利用中序遍历将序列划分为左右子树。假设树的后序遍历为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;
}
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)
//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)
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)
/**
* 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)
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)
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)
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null)
return null;
return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
private TreeNode buildTree(int[] inorder, int inLeft, int inRight, int[] postorder, int postLeft, int postRight) {
if (inLeft > inRight)
return null;
TreeNode root = new TreeNode(postorder[postRight]);
// 只有一个节点，返回root
if (inLeft == inRight)
return root;
int rootNum = 0;
for (int i = inLeft; i <= inRight; i++) {
if (inorder[i] == postorder[postRight]) {
rootNum = i;
break;
}
}
int leftLength = rootNum - inLeft;
//递归左子树和右子树
root.left = buildTree(inorder, inLeft, inLeft + leftLength - 1, postorder, postLeft, postLeft + leftLength - 1);
root.right = buildTree(inorder, inLeft + leftLength + 1, inRight, postorder, postLeft + leftLength,
postRight - 1);
return root;
}
发表于 2017-08-07 09:55:26
回复(0)
问题信息
难度：
85条回答
83收藏
29149浏览
通过挑战的用户
查看代码-
2023-02-17 09:19:27 -
2023-02-13 19:06:59
-
2023-02-13 12:28:12
-
2023-02-12 21:42:43 -
2022-09-11 17:07:52
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
