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

简介: 21_从中序与后序遍历序列构造二叉树

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

给定两个整数数组 inorderpostorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树

示例 1:

输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]

示例 2:

输入:inorder = [-1], postorder = [-1]
输出:[-1]

【思路】

首先回忆一下如何根据两个顺序构造一个唯一的二叉树,就是以后续数组的最后一个元素作为切割点,先切分中序数组,根据中序数组,反过来切分后序数组。一层一层切下去,每次后序数组最后一个元素就是节点元素。

说到一层一层切割,就应该使用递归来做。

  • 第一步:如果数组大小为0的话,说明是空节点了
  • 第二步:如果不为空,那么取后续数组最后一个元素作为节点元素
  • 第三步:找到后序数组最后一个元素在中序数组的位置,作为切割点
  • 第四步:切割中序数组,切成中序左数组和中序右数组
  • 第五步:切割后序数组,切成后序左数组和后序右数组
  • 第六步:递归处理左区间和右区间
TreeNode traversal(int[] inorder, int[] postorder) {
    // 第一步
    if (postorder.size() == 0) 
        return null;
    // 第二步:后序遍历数组最后一个元素,就是当前的中间节点
    int rootValue = postorder[postorder.size() - 1];
    TreeNode root = new TreeNode(rootValue);
    
    // 叶子节点
  if (postorder.size() == 1) return root;
    
    //第三步:找到切割点
    int delimiterIndex;
    for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
        if (inorder[delimiterIndex] == rootValue) break;
    }
    // 第四步:切割中序数组,得到中序左数组和中序右数组
    // 第五步:切割后序数组,得到后序左数组和后序右数组
    //第六步
    root.left = traversal(中序左数组,后序左数组);
    root.right = traversal(中序右数组,后序右数组);
    return root;
}

综合版本

class Solution {
    Map<Integer, Integer> map;  // 方便根据数值查找位置
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }
        return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前闭后开
    }
    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开,说明没有元素,返回空树
            return null;
        }
        int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数,用来确定后序数列的个数
        root.left = findNode(inorder, inBegin, rootIndex,
                            postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                            postorder, postBegin + lenOfLeft, postEnd - 1);
        return root;
    }
}
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder.length == 0 || inorder.length == 0)
            return null;
        return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);
    
    }
    private TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd){
        if(postorderStart == postorderEnd)
            return null;
        int rootVal = postorder[postorderEnd - 1];
        TreeNode root = new TreeNode(rootVal);
        int middleIndex;
        // 中序遍历找到对应的根节点
        for (middleIndex = inorderStart; middleIndex < inorderEnd; middleIndex++){
            if(inorder[middleIndex] == rootVal)
                break;
        }
        int leftInorderStart = inorderStart; //中序左子树开始下标
        int leftInorderEnd = middleIndex; // 根节点的下标 
        int rightInorderStart = middleIndex + 1; //  中序右子树的开始下标
        int rightInorderEnd = inorderEnd;  //  中序结束的下标
        int leftPostorderStart = postorderStart;  // 后序左子树的开始下标
        int leftPostorderEnd = postorderStart + (middleIndex - inorderStart);  // 后序左子树的结束下标,需要通过中序得到的middleIndex的下标来辅助计算
        int rightPostorderStart = leftPostorderEnd;  // 后序右子树的开始下标
        int rightPostorderEnd = postorderEnd - 1;  // 后序右子树的结束下标
        root.left = buildHelper(inorder, leftInorderStart, leftInorderEnd,  postorder, leftPostorderStart, leftPostorderEnd);
        root.right = buildHelper(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostorderStart, rightPostorderEnd);
        return root;
    }  
}
相关文章
|
Java Spring
@Scheduled 多个定时任务同时执行
这篇文章主要介绍了springBoot @Scheduled实现多个任务同时开始执行,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教
1120 0
|
消息中间件 Java Kafka
Java消息队列总结只需一篇解决ActiveMQ、RabbitMQ、ZeroMQ、Kafka
  一、消息队列概述 消息队列中间件是分布式系统中重要的组件,主要解决应用解耦,异步消息,流量削锋等问题,实现高性能,高可用,可伸缩和最终一致性架构。
2973 0
|
JavaScript 前端开发 Java
SpringBoot项目的html页面使用axios进行get post请求
SpringBoot项目的html页面使用axios进行get post请求
179 7
|
机器学习/深度学习 人工智能 运维
自动化运维的魔法:如何利用Python脚本提升工作效率
【9月更文挑战第29天】在数字时代的浪潮中,IT运维人员面临着前所未有的挑战和机遇。本文将通过深入浅出的方式,介绍自动化运维的基本概念、核心价值以及使用Python脚本实现自动化任务的方法。我们将从实际案例出发,探讨如何利用Python简化日常的系统管理任务,提高运维效率,并展望自动化运维的未来趋势。无论你是初学者还是有经验的运维专家,这篇文章都将为你开启一扇通往高效工作方式的大门。
167 2
|
存储 关系型数据库 MySQL
MySQL 为什么使用 B+ 树作为索引结构?
MySQL 为什么使用 B+ 树作为索引结构?
425 2
|
存储 网络协议 Linux
聊一聊 Python 的 socket,以及 select、poll、epoll 又是怎么一回事?
聊一聊 Python 的 socket,以及 select、poll、epoll 又是怎么一回事?
655 2
|
机器学习/深度学习 存储 人工智能
图数据挖掘!使用图分析+AI进行保险欺诈检测 ⛵
本文将基于保险欺诈场景案例讲解如何进行有效的图挖掘,并将挖掘到的信息提供给AI模型,辅助精准检测和识别商业保险欺诈。
4795 1
图数据挖掘!使用图分析+AI进行保险欺诈检测 ⛵
|
前端开发 Go API
Kratos微服务框架API工程化指南
Kratos的RPC默认使用的是[gRPC](https://github.com/grpc/grpc),与此同时我们还可以通过gRPC的[grpc-gateway](https://github.com/grpc-ecosystem/grpc-gateway)功能对RESTfull进行支持。这样,我们就可以同时支持gRPC和REST了。而这一切Kratos都已经封装好,无需知道底层的一切,用就好了。
1753 0
Kratos微服务框架API工程化指南
|
人工智能 搜索推荐 安全
AIGC在医疗诊断中的智能图像应用:推动精准医疗的发展
AIGC在医疗诊断中的智能图像应用:推动精准医疗的发展
1446 0