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;
    }
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • goland 2022.01.13 激活码(注册激活)

    (goland 2022.01.13 激活码)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html40…

  • navicat15永久激活码-激活码分享

    (navicat15永久激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~BI7JCUH1TG-eyJsaWNlbnNlSWQiOi…

  • java tess4j ddl_使用Tess4J碰到的各路问题

    java tess4j ddl_使用Tess4J碰到的各路问题背景:项目需要扫描识别技术,比较了微软(智能识别技术)和谷歌的(Tess4J),决定使用这个开源的东东。建议:1、可以到GitHub找相关的Tess4J项目一、项目结构:使用eclipse构建java项目,下图为项目结构构建TestTess4j.java,(勾选作为main函数)publicclassTestTess4j{publicstaticvoidmain(Stringarg…

  • java 通过Ajax前台传参数 并用 HttpURLConnection Post方式访问对外的接口

    前两天做项目遇到一个问题,就是在自己的项目中要去访问项目外部的接口,从自己的项目中传参数过去,通过调用 对方提供的接口去获取想要得到的数据!第一次接触到在自己项目中去访问和调用外部的资源,然后在网上去找资料,看有没有相关的资料可以参考,然后通过参考其他人的博客资料,最终把这个问题解决了。自己总结一下这个过程,也供遇到相同或者类似问题的朋友可以快速的定位和解决问题。     下面讲一下我的问题和

  • Java零基础学习

    Java零基础学习java0基础1.注释

发表回复

您的电子邮箱地址不会被公开。

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