106. Construct Binary Tree from Inorder and Postorder Traversal「建议收藏」

106. Construct Binary Tree from Inorder and Postorder Traversal「建议收藏」106. Construct Binary Tree from Inorder and Postorder Traversal

大家好,又见面了,我是你们的朋友全栈君。

Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

难度:medium

题目:给定二叉树中序及后序遍历,构造二叉树,注意二叉树中的结点不重复。

思路;分治。

  1. 从后序遍历数组中由后向前取结点r
  2. 在中序遍历中找到r的位置,并由此结点分成两部分,继续执行1.

Runtime: 4 ms, faster than 68.02% of Java online submissions for Construct Binary Tree from Inorder and Postorder Traversal.
Memory Usage: 37.6 MB, less than 42.45% of Java online submissions for Construct Binary Tree from Inorder and Postorder Traversal.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (null == postorder || postorder.length < 1) {
            return null;
        }
        
        return buildTree(inorder, 0, inorder.length - 1, postorder, postorder.length - 1);
    }
    
    public TreeNode buildTree(int[] inorder, int start, int end, int[] postorder, int idx) {
        if (start > end || idx < 0) {
            return null;
        }   
        
        TreeNode root = new TreeNode(postorder[idx]);
        int rIdx = start;
        for (; rIdx <= end; rIdx++) {
            if (inorder[rIdx] == postorder[idx]) {
                break;
            }
        }
        
        root.left = buildTree(inorder, start, rIdx - 1, postorder, idx - (end - rIdx) - 1);
        root.right = buildTree(inorder, rIdx + 1, end, postorder, idx - 1);
        
        return root;
    }
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/106985.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • redis如何设置定时过期_redis 设置过期时间[通俗易懂]

    redis如何设置定时过期_redis 设置过期时间[通俗易懂]1、设置过期时间功能:即对存储在redis数据库中的值可以设置一个过期时间。作为一个缓存数据库,这是非常实用的。如我们一般项目中的token或者一些登录信息,尤其是短信验证码都是有时间限制的,按照传统的数据库处理方式,一般都是自己判断过期,这样无疑会严重影响项目性能。我们setkey的时候,都可以给一个expiretime,就是过期时间,通过过期时间我们可以指定这个key可以…

    2022年9月26日
    1
  • Java中动态代理的两种方式JDK动态代理和cglib动态代理以及区别

    Java中动态代理的两种方式JDK动态代理和cglib动态代理以及区别上篇介绍了一下静态代理:Java中的代理模式——静态代理以及分析静态代理的缺点也分析了一下静态代理的缺点:1、由于静态代理中的代理类是针对某一个类去做代理的,那么假设一个系统中有100个Service,则需要创建100个代理类2、如果一个Service中有很多方法需要事务(增强动作),发现代理对象的方法中还是有很多重复的代码3、由第一点和第二点可以得出:静态代理的重用性不强那怎…

    2022年6月29日
    31
  • j2me开发环境搭建[通俗易懂]

    j2me开发环境搭建[通俗易懂]学习j2me的开发也有半年了,很多东西需要记住并不断实践。 j2me的环境搭建过程。 要准备的东东:1.JDK;2.开发工具Eclipse;3.eclipseMe;4.WTK;   一、下载jdk,并安装,安装好后配置环境变量,假设现在jdk的安装目录是E:/ProgramFiles/Java/jdk1.6.0_10,那么按如下配置环境变量:

    2022年7月11日
    13
  • 深入理解MySQL索引设计和优化原则[通俗易懂]

    深入理解MySQL索引设计和优化原则[通俗易懂]索引类型探讨索引设计和优化原则之前,先给大家熟悉一下索引类型:主键索引PRIMARYKEY:它是一种特殊的唯一索引,不允许有空值。一般是在建表的时候同时创建主键索引。唯一索引UNIQUE:唯一索引列的值必须唯一,但允许有空值。如果是组合索引,则列值的组合必须唯一。创建命令:ALTERTABLEtable_nameADDUNIQUE(column);普通索引INDEX:最基本的索引,它没有任何限制。创建命令:ALTERTABLEtable_nameADDINDEXi..

    2022年6月24日
    22
  • UART配置调试指南[通俗易懂]

    UART配置调试指南[通俗易懂]UART配置(硬件描述)1.根据原理图,查找相关的i2c引脚对应的GPIO值,以GPIO16作为UART1_TX,GPIO17作为UART1_RX为例。2.查找GPIO16与GPIO17对应的BLSP,以及检查GPIO16与GPIO17是否可以作为UART来使用。根据文档,GPIO16与GPIO17对应BLSP3。GPIONUMBERF

    2022年10月18日
    0
  • Angular面试题_angular面试

    Angular面试题_angular面试1.angular的数据绑定采用什么机制?详述原理答案:脏检查机制。解析:双向数据绑定是AngularJS的核心机制之一。当view中有任何数据变化时,会更新到model,当model中数据有变化时,view也会同步更新,显然,这需要一个监控。原理就是,Angular在scope模型上设置了一个监听队列,用来监听数据变化并更新view。每次绑定一个东西到view上时AngularJS就会往$watch队列里插入一条$watch,用来检测它监视的mode

    2022年10月18日
    0

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号