给定一个二叉树的中序与后序遍历结果，请你根据两个序列构造符合这两个序列的二叉树。
数据范围：二叉树的节点数满足 
，节点上的值满足 
，保证节点的值各不相同
例如输入[2,1,4,3,5],[2,4,5,3,1]时，
根据中序遍历的结果[2,1,4,3,5]和后序遍历的结果[2,4,5,3,1]可构造出二叉树{1,2,3,#,#,4,5}，如下图所示：
[编程题]从中序与后序遍历序列构造二叉树
分治重构求解。中序遍历的顺序为：左中右；后序遍历的顺序为：左右中。因此后续遍历序列的最后一个元素为根节点，我们找到它在中序遍历中的位置，就可以把中序遍历序列划分为左右两部分，分别为左右子树的中序遍历序列；而根据中序遍历划分出来的左右子树的元素个数，我们又可以把后序遍历序列划分为左右两个部分。然后两个序列的左右部分分别走相同的过程进行递归重构，构建出根节点的左子树和右子树。
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param inorder int整型一维数组 中序遍历序列
* @param postorder int整型一维数组 后序遍历序列
* @return TreeNode类
*/
public TreeNode buildTree (int[] inorder, int[] postorder) {
// write code here
if(inorder.length != postorder.length || inorder == null || inorder.length == 0) return null;
int rootVal = postorder[postorder.length - 1]; // 后序遍历的最后一个元素是根节点
TreeNode tree = new TreeNode(rootVal); // 构建根节点
// 找到根节点在中序遍历中的位置
int rootIndex = 0;
for(int i = 0; i < inorder.length; i++){
if(inorder[i] == rootVal){
rootIndex = i;
break;
}
}
// 将序列划分为左右两个子树部分，分别进行重构
tree.left = buildTree(Arrays.copyOfRange(inorder, 0, rootIndex), Arrays.copyOfRange(postorder, 0, rootIndex));
tree.right = buildTree(Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length), Arrays.copyOfRange(postorder, rootIndex, postorder.length - 1));
return tree;
}
}
发表于 2021-12-11 11:30:34
回复(0)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param inorder int整型vector 中序遍历序列
* @param postorder int整型vector 后序遍历序列
* @return TreeNode类
*/
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// write code here
if (postorder.empty()) return nullptr;
TreeNode *root = new TreeNode(postorder[postorder.size() - 1]);
vector<int> left, right;
for (int i = 0; i < inorder.size(); ++i) {
if (inorder[i] == root->val) {
// left
vector<int> left_in(inorder.begin(), inorder.begin() + i);
vector<int> left_post(postorder.begin(), postorder.begin() + i);
root->left = buildTree(left_in, left_post);
// right
vector<int> right_in(inorder.begin() + i + 1, inorder.end());
vector<int> right_post(postorder.begin() + i, postorder.end() - 1);
root->right = buildTree(right_in, right_post);
}
}
return root;
}
};
发表于 2022-07-19 17:48:50
回复(0)
这道题与从中序和先序遍历恢复二叉树的题思路一样的
① 后续遍历数组最后一个元素即是根节点位置，再找到中序遍历的位置
② 中序遍历根节点位置的右边第一个便是根节点的右节点，该节点的位置就是在后续遍历的倒数第二位
③ 恢复右节点的时候递归处理，将他的所有子树使用同样的逻辑一并恢复
④ 右边节点全部恢复完成，再逆序取后续遍历数组的下个元素，则为根节点的左边节点
⑤ 恢复根节点的左边节点，同样递归处理，过程跟上述完全一样
⑥ 退出条件就是当前根节点为 NULL （start > end）或者再无子节点(start == end)，这是关键
public TreeNode buildTree(int[] inorder, int[] postorder) {
// write code here
postIndex = postorder.length - 1;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; i++)
map.put(inorder[i],
i);// 题目声明了值不一样，则可用map记录中序遍历的位置信息
return recurHelper(0, postIndex, postorder, map);
}
private static int postIndex = 0;
public TreeNode recurHelper(int start, int end, int[] postorder,
Map<Integer, Integer> imap) {
if(start > end) return null;
TreeNode currRoot = new TreeNode(postorder[postIndex--]);
if (start == end) return currRoot;
Integer currIdx = imap.get(currRoot.val);
currRoot.right = recurHelper(currIdx + 1, end, postorder, imap);
currRoot.left = recurHelper(start, currIdx - 1, postorder, imap);
return currRoot;
}
发表于 2024-09-13 17:11:43
回复(0)
不改动参数的递归解法
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// write code here
if(inorder.size()==0||postorder.size()==0) return nullptr;
int x=*postorder.rbegin();
TreeNode *root=new TreeNode(x);
int post;
for(int i=0;i<inorder.size();i++)
{
if(inorder[i]==x) post=i;
}
vector<int> lin;
vector<int> rin;
for(int i=0;i<post;i++) lin.push_back(inorder[i]);
for(int i=post+1;i<inorder.size();i++) rin.push_back(inorder[i]);
vector<int>lpost;
vector<int>rpost;
for(int i=0;i<post;i++)lpost.push_back(postorder[i]);
for(int i=post;i<postorder.size()-1;i++)rpost.push_back(postorder[i]);
root->left=buildTree(lin, lpost);
root->right=buildTree(rin, rpost);
return root;
}
编辑于 2024-03-23 19:20:29
回复(0)
C语言代码实现：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param inorder int整型一维数组 中序遍历序列
* @param inorderLen int inorder数组长度
* @param postorder int整型一维数组 后序遍历序列
* @param postorderLen int postorder数组长度
* @return TreeNode类
*/
struct TreeNode* buildTree(int* inorder, int inorderLen, int* postorder, int postorderLen ) {
// write code here
if (inorderLen < 1 || postorderLen < 1)return NULL;
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = postorder[postorderLen - 1];
int* p = inorder;
for (; p < inorder + inorderLen; p++) {
if (*p == postorder[postorderLen - 1])
break;
}
int k = p - inorder; //左子树结点数量
//递归构建左子树：中序开始位置inorder，后序开始位置postorder
root->left = buildTree(inorder, k, postorder, k);
//右子树结点数量inorderLen - k - 1
//递归构建右子树：中序开始位置p+1，后序开始位置postorder+k
root->right = buildTree(p + 1, inorderLen - k - 1, postorder + k, inorderLen - k - 1);
return root;
}
//前序遍历
void preOrder(struct TreeNode* root) {
if (root) {
printf("%d ", root->val);
preOrder(root->left);
preOrder(root->right);
}
}
int main(int argc, char *argv[])
{
int inorder[] = {2, 1, 4, 3, 5};
int postorder[] = {2, 4, 5, 3, 1};
int n = sizeof(inorder) / sizeof(int);
struct TreeNode* root = buildTree(inorder, n, postorder, n);
preOrder(root);
printf("\n");
return 0;
}
发表于 2023-10-15 18:53:49
回复(0)
简介优雅，这才是好代码。
int post_idx;
TreeNode* build(int i1, int i2, vector<int>& inorder, vector<int>& postorder){
if(i1 > i2)
return nullptr;
vector<int>::iterator it = find(inorder.begin() + i1, inorder.begin() + i2 + 1, postorder[post_idx]);
int idx = distance(inorder.begin(), it);
TreeNode *newNode = new TreeNode(inorder[idx]);
post_idx --;
newNode->right = build(idx +1, i2, inorder, postorder);
newNode->left = build(i1, idx - 1, inorder, postorder);
return newNode;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
post_idx = postorder.size() - 1;
return build(0, inorder.size() - 1, inorder, postorder);
}
发表于 2023-03-21 23:05:20
回复(0)
/*
* function TreeNode(x) {
* this.val = x;
* this.left = null;
* this.right = null;
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param inorder int整型一维数组 中序遍历序列
* @param postorder int整型一维数组 后序遍历序列
* @return TreeNode类
*/
function buildTree(inorder, postorder) {
// write code here
if (postorder.length === 0) return null;
let val = postorder[postorder.length - 1];
let index = inorder.indexOf(val);
let in1 = inorder.slice(0, index);
let in2 = inorder.slice(index + 1);
let post1 = postorder.slice(0, index);
let post2 = postorder.slice(index, postorder.length - 1);
let root= new TreeNode(val);
root.left = buildTree(in1, post1);
root.right = buildTree(in2, post2);
return root
}
module.exports = {
buildTree: buildTree,
};
发表于 2025-05-30 10:28:49
回复(0)
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param inorder int整型一维数组 中序遍历序列
# @param postorder int整型一维数组 后序遍历序列
# @return TreeNode类
#
class Solution:
def buildTree(self , inorder: List[int], postorder: List[int]) -> TreeNode:
# write code here
def dfs(inorder,postorder):
if not inorder or not postorder:
return None
root = TreeNode(postorder[-1])
index = inorder.index(postorder[-1])
#[left,right,root] [left root right]
root.left = dfs(inorder[:index],postorder[:index])
root.right = dfs(inorder[index+1:],postorder[index:-1])
return root
return dfs(inorder,postorder)
发表于 2025-05-13 17:27:24
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
/**
* NC223 从中序与后序遍历序列构造二叉树
* @author d3y1
*/
public class Solution {
HashMap<Integer,Integer> inMap = new HashMap<>();
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 相似 -> NC12 重建二叉树 [nowcoder]
*
* @param inorder int整型一维数组 中序遍历序列
* @param postorder int整型一维数组 后序遍历序列
* @return TreeNode类
*/
public TreeNode buildTree (int[] inorder, int[] postorder) {
// return solution1(inorder, postorder);
// return solution2(inorder, postorder);
// return solution22(inorder, postorder);
return solution3(inorder, postorder);
}
/**
* 递归
* @param inorder
* @param postorder
* @return
*/
private TreeNode solution1(int[] inorder, int[] postorder){
return construct(inorder, postorder);
}
/**
* 递归
* @param inorder
* @param postorder
* @return
*/
public TreeNode construct(int[] inorder, int[] postorder){
int n = postorder.length;
if(n == 0){
return null;
}
// 当前根结点
int rootVal = postorder[n-1];
TreeNode root = new TreeNode(rootVal);
// 当前根结点 左子树节点个数
int left = 0;
while(inorder[left] != rootVal){
left++;
}
if(left > 0){
root.left = construct(Arrays.copyOfRange(inorder, 0, left), Arrays.copyOfRange(postorder, 0, left));
}
// 当前根结点 右子树节点个数
int right = n-(left+1);
if(right > 0){
root.right = construct(Arrays.copyOfRange(inorder, left+1, n), Arrays.copyOfRange(postorder, left, n-1));
}
return root;
}
//////////////////////////////////////////////////////////////////////////////////////
/**
* 哈希 + 递归
* @param inorder
* @param postorder
* @return
*/
private TreeNode solution2(int[] inorder, int[] postorder){
int n = inorder.length;
if(n == 0){
return null;
}
// 哈希: val -> idx
for(int i=0; i<n; i++){
inMap.put(inorder[i], i);
}
// 根结点
TreeNode root = new TreeNode(postorder[n-1]);
// 递归遍历
dfs(postorder, root, 0, n-1, 0, n-1);
return root;
}
/**
* 递归遍历
* @param postorder
* @param root
* @param inLeft
* @param inRight
* @param postLeft
* @param postRight
*/
private void dfs(int[] postorder, TreeNode root, int inLeft, int inRight, int postLeft, int postRight){
int inRootIdx = inMap.get(root.val);
int leftSize = inRootIdx-inLeft;
int rightSize = inRight-inRootIdx;
// 有左子树
if(leftSize > 0){
root.left = new TreeNode(postorder[postLeft+leftSize-1]);
dfs(postorder, root.left, inLeft, inRootIdx-1, postLeft, postLeft+leftSize-1);
}
// 有右子树
if(rightSize > 0){
root.right = new TreeNode(postorder[postRight-1]);
dfs(postorder, root.right, inRootIdx+1, inRight, postLeft+leftSize, postRight-1);
}
}
//////////////////////////////////////////////////////////////////////////////////////
/**
* 哈希+递归: 简化
* @param inorder
* @param postorder
* @return
*/
private TreeNode solution22(int[] inorder, int[] postorder){
int n = inorder.length;
if(n == 0){
return null;
}
// 哈希: val -> idx
for(int i=0; i<n; i++){
inMap.put(inorder[i], i);
}
// 递归遍历
return dfs(postorder, 0, n-1, 0, n-1);
}
/**
* 递归遍历: 简化
* @param postorder
* @param inLeft
* @param inRight
* @param postLeft
* @param postRight
*/
private TreeNode dfs(int[] postorder, int inLeft, int inRight, int postLeft, int postRight){
TreeNode root = new TreeNode(postorder[postRight]);
int inRootIdx = inMap.get(root.val);
int leftSize = inRootIdx-inLeft;
int rightSize = inRight-inRootIdx;
// 有左子树
if(leftSize > 0){
root.left = dfs(postorder, inLeft, inRootIdx-1, postLeft, postLeft+leftSize-1);
}
// 有右子树
if(rightSize > 0){
root.right = dfs(postorder, inRootIdx+1, inRight, postLeft+leftSize, postRight-1);
}
return root;
}
//////////////////////////////////////////////////////////////////////////////////////
// 后序遍历根结点索引
private int postRootIdx;
private TreeNode solution3(int[] inorder, int[] postorder){
int n = postorder.length;
postRootIdx = n-1;
// 哈希: val -> idx
for(int i=0; i<n; i++){
inMap.put(inorder[i], i);
}
return build(postorder, 0, n-1);
}
/**
* 递归遍历
*
* 二叉树后序遍历: 左 -> 右 -> 根
* 可利用该性质直接找到后序遍历根节点, 子树遍历先右后左: (根) -> 右 -> 左
*
* @param postorder
* @param inLeft
* @param inRight
* @return
*/
private TreeNode build(int[] postorder, int inLeft, int inRight){
if(inLeft > inRight){
return null;
}
// 根
int postRootVal = postorder[postRootIdx--];
TreeNode root = new TreeNode(postRootVal);
if(inLeft == inRight){
return root;
}
// 中序遍历根结点索引
int inRootIdx = inMap.get(postRootVal);
// 右
root.right = build(postorder, inRootIdx+1, inRight);
// 左
root.left = build(postorder, inLeft, inRootIdx-1);
return root;
}
}
发表于 2025-01-06 13:33:53
回复(0)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param inorder int整型一维数组 中序遍历序列
* @param inorderLen int inorder数组长度
* @param postorder int整型一维数组 后序遍历序列
* @param postorderLen int postorder数组长度
* @return TreeNode类
*/
#include <stdlib.h>
struct TreeNode* buildTree(int* inorder, int inorderLen, int* postorder, int postorderLen ) {
// write code here
if (inorderLen==1) {
struct TreeNode *tree=(struct TreeNode*)malloc(sizeof(struct TreeNode));
tree->val=*inorder,tree->left=NULL,tree->right=NULL;
return tree;
}
else{
struct TreeNode *tree=(struct TreeNode*)malloc(sizeof(struct TreeNode));
tree->val=*(postorder+postorderLen-1);
int i=0;
for (i=0;i<inorderLen;i++) {
if (inorder[i]==postorder[postorderLen-1]){
break;
}
}
tree->left=buildTree(inorder,i,postorder,i);
tree->right=buildTree(inorder+i+1,inorderLen-1-i,postorder+i,postorderLen-1-i);
return tree;
}
}
发表于 2024-11-21 10:10:51
回复(0)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param inorder int整型一维数组 中序遍历序列
* @param inorderLen int inorder数组长度
* @param postorder int整型一维数组 后序遍历序列
* @param postorderLen int postorder数组长度
* @return TreeNode类
*/
struct TreeNode* buildTree(int* inorder, int inorderLen, int* postorder, int postorderLen ) {
if(inorderLen<1 || postorderLen<1) return NULL;
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = postorder[postorderLen-1];
int leftnum=0;
for(leftnum=0; leftnum<inorderLen; leftnum++)
{
if(*(inorder+leftnum) == root->val)
break;
}
if(leftnum == inorderLen) leftnum--;
root->left = buildTree(inorder, leftnum, postorder, leftnum);
root->right = buildTree(inorder+leftnum+1, inorderLen-leftnum-1, postorder+leftnum, postorderLen-leftnum-1);
return root;
// write code here
}
重点在与想清楚递归里面的中序的左右子树的位置和后序左右子树的位置
发表于 2024-08-14 17:10:43
回复(0)
class Solution:
def buildTree(self , inorder: List[int], postorder: List[int]) -> TreeNode:
root=TreeNode(postorder[-1])
self.bt(inorder,postorder,root)
return root
def bt(self,inorder,postorder,root):
# write code here
if root:
c=inorder.index(root.val)
left=inorder[0:c]
right=inorder[c+1:]
rr=postorder[-(len(right)+1):-1]
rl=postorder[:-(len(right)+1)]
if rl:
root.left=TreeNode(rl[-1])
self.bt(left,rl,root.left)
if rr:
root.right=TreeNode(rr[-1])
self.bt(right,rr,root.right)
else:
return None
发表于 2024-08-07 16:08:14
回复(0)
package main
//import "fmt"
import . "nc_tools"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param inorder int整型一维数组 中序遍历序列
* @param postorder int整型一维数组 后序遍历序列
* @return TreeNode类
*/
func buildTree( inorder []int , postorder []int ) *TreeNode {
// write code here
if len(postorder) == 0{
return nil
}
newNode := new(TreeNode)
newNode.Val = postorder[len(postorder) - 1]
for i := 0; i < len(inorder); i++{
if newNode.Val == inorder[i]{
newNode.Left = buildTree(inorder[:i], postorder[:i])
newNode.Right = buildTree(inorder[i+1:], postorder[i:len(postorder)-1])
return newNode
}
}
return newNode
}
发表于 2024-04-11 22:09:09
回复(0)
c语言
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
#include <stdlib.h>
void build_root(struct TreeNode** root,int* inorder,int left1,int right1,int* postorder, int* idx){
if(left1 > right1 || *idx == -1){
return;
}
*root = malloc(sizeof(struct TreeNode));
printf("%d ",postorder[*idx]);
(*root)->val = postorder[*idx];
(*idx)--;
(*root)->left = NULL;
(*root)->right = NULL;
//找到postOrder[*idx]在inorder的位置
for(int i = left1; i <= right1;i++){
if(inorder[i] == (*root)->val){ //找到
//判断*idx 是否已经走完
if(*idx != -1){
//判断下一个根节点的位置是在inorder[i]的左边还是右边
int flag = 1;//1右边，0左边
for(int j = left1; j <= i;j++){
if(inorder[i] ==postorder[*idx]){
//在左边
flag = 0;
break;
}
}
if(flag == 0){
build_root(&((*root)->left), inorder, left1, i-1,postorder, idx);
build_root(&((*root)->right), inorder, i+1, right1,postorder, idx);
} else {
build_root(&((*root)->right), inorder, i+1, right1,postorder, idx);
build_root(&((*root)->left), inorder, left1, i-1,postorder, idx);
}
}
break;
}
}
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param inorder int整型一维数组 中序遍历序列
* @param inorderLen int inorder数组长度
* @param postorder int整型一维数组 后序遍历序列
* @param postorderLen int postorder数组长度
* @return TreeNode类
*/
struct TreeNode* buildTree(int* inorder, int inorderLen, int* postorder, int postorderLen ) {
// write code here
//记录节点数为1000个，记录输入值中
struct TreeNode* root;
int idx = postorderLen-1;
build_root(&root, inorder, 0, inorderLen - 1, postorder,&idx);
return root;
}
编辑于 2024-02-18 17:54:23
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param inorder int整型一维数组 中序遍历序列
* @param postorder int整型一维数组 后序遍历序列
* @return TreeNode类
*/
public TreeNode buildTree (int[] inorder, int[] postorder) {
// write code here
return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
// 左 中 右
// 左 右 中
private TreeNode build(int[] inOrder, int li, int ri, int[] postorder, int lp, int rp) {
if(li > ri) return null;
TreeNode cur = new TreeNode(postorder[rp]);
int i = li;
for(; i <= ri; i++) {
if(inOrder[i] == postorder[rp]) break;
}
cur.left = build(inOrder, li, i - 1, postorder, lp, lp + i - li - 1);
// ri - i - 1
cur.right = build(inOrder, i + 1, ri, postorder, rp - ri + i, rp - 1);
return cur;
}
}
发表于 2024-02-06 02:11:27
回复(0)
/**
* struct TreeNode {
* int val;
* struct TreeNode* left;
* struct TreeNode* right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
int post_idx; // 从后序遍历的 最后一个元素开始
unordered_map<int, int> idx_map;// 建立（中序元素，后序下标）键值对的哈希表
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// 从后序遍历的最后一个元素开始
post_idx = (int)postorder.size()-1;
int idx = 0; // 建立（中序元素，中序下标）键值对的哈希表
for (auto& val : inorder)
idx_map[val] = idx++;
return helper(0, (int)inorder.size()-1, inorder, postorder);
}
TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){
if (in_left > in_right) // 如果这里没有节点构造二叉树了，就结束
return nullptr;
int root_val = postorder[post_idx]; //1 选择post_idx位置的元素，作为当前子树 根节点
post_idx--; // 下标减一
TreeNode* root = new TreeNode(root_val); // 根节点
int index = idx_map[root_val]; //2 根据root所在中序的index，将中序分成左右两棵子树
root->right = helper(index+1, in_right, inorder, postorder); // 1构造root节点的右子树
root->left = helper(in_left, index-1, inorder, postorder); // 2构造root节点的左子树
return root; // 根节点
}
};
发表于 2023-09-24 17:02:41
回复(0)
划分左右子叶的思想解题。
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
#include <unordered_map>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param inorder int整型vector 中序遍历序列
* @param postorder int整型vector 后序遍历序列
* @return TreeNode类
*/
TreeNode* buildTreehelper(vector<int>& inorder, int instart, int inend, vector<int>& postorder, int poststart, int postend, unordered_map<int, int>& map){
if(instart > inend || poststart > postend){
return nullptr; // 递归终止条件
}
// 在后续数组中找根节点
TreeNode* root = new TreeNode(postorder[postend]);
int rootIndex = map[postorder[postend]];
// 根据中序数组分割左右子树
// 中序数组中的左片段[instart, rootIndex - 1] ***
// 中序数组中的右片段[rootIndex + 1, inend]
// 后续数组中的左片段[poststart, poststart + (rootIndex - instart) - 1] ***
// 后续数组中的右片段[poststart + (rootIndex - instart), postend - 1]
root->left = buildTreehelper(inorder, instart, rootIndex - 1, postorder, poststart, poststart + (rootIndex - instart) - 1, map);
root->right = buildTreehelper(inorder, rootIndex + 1, inend, postorder, poststart + (rootIndex - instart), postend - 1, map);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// 先把中序数组的位置用哈希表存起来，方便查找
unordered_map<int, int> map;
for(int i = 0; i < inorder.size(); i++){
map[inorder[i]] = i;
}
return buildTreehelper(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1, map);
}
};
发表于 2023-07-26 12:06:26
回复(0)
class Solution:
def buildTree(self , inorder: List[int], postorder: List[int]) -> TreeNode:
def build(pos_left, pos_right, mid_left, mid_right):
if pos_left > pos_right or mid_left > mid_right: # 停止条件
return None
root = TreeNode(postorder[pos_right]) # 构建节点
mid_root = mid_left
while mid_root <= mid_right and inorder[mid_root] != postorder[pos_right]: #找寻根节点
mid_root += 1
diff = mid_root - mid_left # 左子树的长度
root.left = build(pos_left, pos_left + diff -1, mid_left, mid_root - 1) # 构建左子树
root.right = build(pos_left + diff, pos_right - 1, mid_root + 1, mid_right) # 构建右子树
return root # 返回构建好的树
return build(0, len(postorder) - 1, 0, len(inorder) - 1)
发表于 2023-07-21 12:59:02
回复(1)
/*
* function TreeNode(x) {
* this.val = x;
* this.left = null;
* this.right = null;
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param inorder int整型一维数组 中序遍历序列
* @param postorder int整型一维数组 后序遍历序列
* @return TreeNode类
*/
function buildTree( inorder , postorder ) {
if(postorder.length==0) return null;
let root_val=postorder[postorder.length-1];
let idx=inorder.indexOf(root_val);
let root=new TreeNode(root_val);
root.left=buildTree(inorder.slice(0,idx),postorder.slice(0,idx));
root.right=buildTree(inorder.slice(idx+1),postorder.slice(idx,postorder.length-1));
return root;
}
module.exports = {
buildTree : buildTree
};
发表于 2022-11-15 14:06:08
回复(0)
问题信息
难度：
29条回答
145收藏
8435浏览
通过挑战的用户
查看代码-
2022-11-04 08:18:48
-
2022-09-15 18:17:58 -
2022-09-15 16:37:49 -
2022-09-14 23:42:26
-
2022-09-14 19:37:13
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
