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)


相关推荐

  • generic host process已停止工作_host error怎么修复

    generic host process已停止工作_host error怎么修复GenericHostProcessforWin32开机后总是提示出现错误需要关闭GenericHostProcessforWin32Services错误解决办法出现上面这个错误一般有三种情况。1.就是病毒。开机后会提示GenericHostProcessforWin32Services遇到问题需要关闭”“RemoteRro…

    2022年10月10日
  • idea卸载删除旧版重新安装新版后,新版本idea程序打不开闪退的解决方案

    idea卸载删除旧版重新安装新版后,新版本idea程序打不开闪退的解决方案一般情况下,都是因为激活成功教程idea时,在启动参数配置文件idea64.exe.vmoptions中添加了如下参数:-javaagent:D:\IntelliJIDEA2020.1\bin\jetbrainsCrack.jar指定了一个jar文件,而新的idea会复制该配置文件,拿来直接使用,但是如果这个jar文件不存在,那么新安装的idea就打不开。解决方案需要将idea的idea64.exe.vmoptions配置文件中上面那个参数删除掉即可,但idea64.exe.vmoptions配置

  • Linux 删除文件夹和文件的命令

    Linux 删除文件夹和文件的命令

    2021年10月14日
  • 服务器文件句柄数_Linux文件句柄机制

    服务器文件句柄数_Linux文件句柄机制设置文件句柄在配置我们的RedHatLinux服务器时,确保文件句柄的最大数量足够大是非常关键的。文件句柄设置表示您在Linux系统中可以打开的文件数量。使用以下命令来确定整个系统中文件句柄的最大数量:#cat/proc/sys/fs/file-max32768Oracle建议将整个系统的文件句柄值至少设置为65536。通过直接更改/proc文件系统,您可以不必重新启动机…

    2022年10月18日
  • Linux Epoll介绍和程序实例

    Linux Epoll介绍和程序实例

  • Delphi语言_DELPHI

    Delphi语言_DELPHI总结一下SQL语句中引号(‘)、quotedstr()、(”)、format()在SQL语句中的用法以及SQL语句中日期格式的表示(#)、(”)在Delphi中进行字符变量连接相加时单引号用(”’),又引号用(””)表示首先定义变量var AnInt:integer=123;//为了方便在此都给它们赋初值。虽然可能在引赋初值在某些情况下不对AnIntStr:str

    2022年10月18日

发表回复

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

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