我要招人

去企业版

首页 > 试题广场 >

从中序与后序遍历序列构造二叉树

[编程题]从中序与后序遍历序列构造二叉树

热度指数：5591 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个二叉树的中序与后序遍历结果，请你根据两个序列构造符合这两个序列的二叉树。

数据范围：二叉树的节点数满足 $1 \le n \le 1000 \$ ，节点上的值满足 $|val| \le 10^9 \$ ，保证节点的值各不相同

例如输入[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}，如下图所示：

示例1

输入

[1],[1]

输出

{1}

示例2

输入

[2,1,4,3,5],[2,4,5,3,1]

输出

{1,2,3,#,#,4,5}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Java

dxw-1997

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)

Java

紫薇爸爸

思路：

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)

Java

菲尼克斯弗兰克

// 先构造根节点再递归左右子树，关键在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)

Java

pein531

分治重构求解。中序遍历的顺序为：左中右；后序遍历的顺序为：左右中。因此后续遍历序列的最后一个元素为根节点，我们找到它在中序遍历中的位置，就可以把中序遍历序列划分为左右两部分，分别为左右子树的中序遍历序列；而根据中序遍历划分出来的左右子树的元素个数，我们又可以把后序遍历序列划分为左右两个部分。然后两个序列的左右部分分别走相同的过程进行递归重构，构建出根节点的左子树和右子树。

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)