博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Construct Binary Tree from Inorder and Postorder Traversal
阅读量:7177 次
发布时间:2019-06-29

本文共 920 字,大约阅读时间需要 3 分钟。

思路和依据前序遍历和中序遍历重建树的思路一样,复杂度也一致,代码如下:

class Solution(object):    def buildTree(self, inorder, postorder):        """        :type inorder: List[int]        :type postorder: List[int]        :rtype: TreeNode        """        if not inorder:            return None        length = len(inorder)        map = {}        for i in xrange(length):            map[inorder[i]] = i        return self.helper(postorder,0,length-1,0,length-1,map)                def helper(self,postorder,Istart,Iend,Pstart,Pend,map):        if Istart > Iend:            return None        node = TreeNode(postorder[Pend])        if Istart == Iend:            return node        index = map[node.val]        node.left = self.helper(postorder,Istart,index-1, Pstart,Pstart+index-Istart-1,map)        node.right = self.helper(postorder,index+1,Iend,Pstart+index-Istart,Pend-1,map)        return node

 

转载于:https://www.cnblogs.com/sherylwang/p/5405724.html

你可能感兴趣的文章
Linux 网卡重命名
查看>>
cisco1226
查看>>
Linux的yum与list结合
查看>>
详解Python 采用 requests + Beautiful Soup 爬取房天下新楼盘推荐
查看>>
Linux 命令历史
查看>>
我的友情链接
查看>>
Oracle Dataguard报错:ARC1: Becoming the 'no FAL' ARC
查看>>
COQ Soft-表格样式
查看>>
centos7 的系统服务
查看>>
聚焦百度年会美女刘冬——IT听听看特别版
查看>>
加超链接
查看>>
OpenStack控制台console偶尔无法使用或加载慢
查看>>
使用X-Frame-Options防止网页被Frame
查看>>
NIO入门系列之第6章:分散和聚集
查看>>
奔跑中的2015——有时候我们需要慢下来
查看>>
Xshell使用root用户连接Ubuntu14.04时,提示SSH服务器拒绝了密码,请再试一次
查看>>
Citrx XenDesktop 7 实施七 创建桌面组
查看>>
EF 控制code-first生成的数据库表名的单复数
查看>>
2014.10.1 Cmd更改系统时间
查看>>
关于浏览器缓冲
查看>>