首页 > 其他 > 详细

Construct Binary Tree from Inorder and Postorder Traversal

时间:2016-04-18 21:58:30      阅读:180      评论:0      收藏:0      [点我收藏+]

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

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

 

Construct Binary Tree from Inorder and Postorder Traversal

原文:http://www.cnblogs.com/sherylwang/p/5405724.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!