给定一个二叉树的中序与后序遍历结果，请你根据两个序列构造符合这两个序列的二叉树。
数据范围：二叉树的节点数满足 
，节点上的值满足 
，保证节点的值各不相同
例如输入[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;
* }
* }
*/
/**
* 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)
1.用哈希表存储中序的值和索引（可以使用for循环的方式来找寻根节点在中序的索引），索引用于左右子树的划分
2.构建划分函数
1.递归出口，左大于右结束。
2.根节点值为后序的最后一个节点并在中序遍历中找到这个值（将他左右划分，左边为左子树，右边为右子树）
3.创建节点。值为上述找出的值
4.递归的划分左右子树，并返回创建的节点，不一定是最终的根节点
3.返回根节点
int[] post;
HashMap<Integer,Integer> inorderMap = new HashMap<Integer,Integer>();
public TreeNode buildTree (int[] inorder, int[] postorder) {
for(int i = 0;i<inorder.length;i++){
inorderMap.put(inorder[i],i);
}
// write code here
post = postorder;
int len = inorder.length;
return build(0,len - 1,0,len -1);
}
private TreeNode build(int inleft,int inright,int postleft,int postright){
if(inleft > inright || postleft > postright){
return null;
}
int value = post[postright];
int index = inorderMap.get(value);
TreeNode root = new TreeNode(value);
root.left = build(inleft,index - 1,postleft,postleft+index-inleft -1);
root.right = build(index+1,inright,postleft+index-inleft,postright -1);
return root;
}
发表于 2022-02-22 12:38:16
回复(0)
思路：
1.中序遍历顺序:左根右；后序遍历顺序：左右根；根据给出的后序遍历数组可知，数组末元素为根结点值；取出该结点，作为根结点的值。
2.根据中序遍历顺序，找出根结点位置rootIdx；在中序遍历数组中，该结点左边元素为左子树结点值，右边为右子树结点值；在后序遍历数组中，可知从0到rootIdx为左子树结点，从rootIdx到倒数第二个元素为右子数结点。
3.根据中序遍历左子数，后序遍历左子数数组初始化左子树，作为根结点的左子树；根据中序遍历右子数，后序遍历右子数数组初始化右子树，作为根结点的右子树；
4.返回根结点
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[] midorder, int[] postorder) {
// write code here
//用递归的方式，从上向下逐渐构建二叉树
//无结点
if(midorder.length==0 || midorder==null || midorder.length!=postorder.length)
return null;
else if(midorder.length==1 && midorder.length==postorder.length){ //1个节点
TreeNode root = new TreeNode(midorder[0]);
root.left=null;
root.right=null;
return root;
}
//多个节点
int len = midorder.length;
int val = postorder[len-1];
TreeNode root = new TreeNode(val);
int index=0; //根节点，用于记录其在中序遍历中的索引值
for(int i=0;i<len;i++){
if(val==midorder[i])
index = i;
}
root.left = buildTree( Arrays.copyOfRange(midorder,0,index), Arrays.copyOfRange(postorder,0,index) );
root.right = buildTree(Arrays.copyOfRange(midorder,index+1,len), Arrays.copyOfRange(postorder,index,len-1) );
return root;
}
}
发表于 2022-02-22 11:24:51
回复(0)
// 先构造根节点再递归左右子树，关键在help辅助函数的下标如何写
public class Solution {
public TreeNode buildTree (int[] inorder, int[] postorder) {
for (int i = 0; i < inorder.length; i++)
map.put(inorder[i], i);
return help(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
}
public Map<Integer, Integer> map = new HashMap<>();
public TreeNode help(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd) {
if (inStart > inEnd) return null;
int idx = map.get(postorder[postEnd]);
int l = idx - inStart;
TreeNode root = new TreeNode(postorder[postEnd]);
root.left = help(inorder, inStart, idx-1,
postorder, postStart, postStart+l-1);
root.right = help(inorder, idx+1, inEnd,
postorder, postStart+l, postEnd-1);
return root;
}
}
发表于 2022-01-04 16:30:41
回复(1)
分治重构求解。中序遍历的顺序为：左中右；后序遍历的顺序为：左右中。因此后续遍历序列的最后一个元素为根节点，我们找到它在中序遍历中的位置，就可以把中序遍历序列划分为左右两部分，分别为左右子树的中序遍历序列；而根据中序遍历划分出来的左右子树的元素个数，我们又可以把后序遍历序列划分为左右两个部分。然后两个序列的左右部分分别走相同的过程进行递归重构，构建出根节点的左子树和右子树。
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)
问题信息
难度：
6条回答
145收藏
8564浏览
通过挑战的用户
查看代码-
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号
