Construct Binary Tree from Preorder and Inorder Traversal @ LeetCode (Python)
Remove Duplicates from Sorted List II @ LeetCode (Python)

Construct Binary Tree from Inorder and Postorder Traversal @ LeetCode (Python)

kitt posted @ 2014年4月14日 14:02 in LeetCode , 4045 阅读

 

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
 
class Solution:
    # @param inorder, a list of integers
    # @param postorder, a list of integers
    # @return a tree node
    def buildTree(self, inorder, postorder):
        if not inorder: return None # inorder is empty
        self.inorder, self.postorder = inorder, postorder
        return self.dfs(0, 0, len(inorder))
    
    def dfs(self, inLeft, postLeft, Len):
        if Len <= 0:
            return None
        root = TreeNode(self.postorder[postLeft + Len - 1])
        rootPos = self.inorder.index(self.postorder[postLeft + Len - 1])
        root.left = self.dfs(inLeft, postLeft, rootPos - inLeft)
        root.right = self.dfs(rootPos + 1, postLeft + rootPos - inLeft, Len - 1 - (rootPos - inLeft))
        return root
Avatar_small
lhq 说:
2015年3月17日 09:46

这个代码提交了提示Memory Limit Exceeded,我写的代码也是这个错误,你提交成功了么?

Avatar_small
kitt 说:
2015年3月19日 01:49

之前提交成功了,现在也是Memory Limit Exceeded, 看来要求更严格了啊@lhq:

Avatar_small
lhq 说:
2015年3月19日 04:52

我后来改好了,列表切片是产生新的列表,以前的列表没有释放,所以会造成内存溢出,只要建一个类变量,然后递归列表的区间位置变量就行了@kitt:

Avatar_small
kitt 说:
2015年3月20日 02:37

我觉得用实例变量更好吧,上面代码已更新了,你瞅一下~@lhq:

Avatar_small
lhq 说:
2015年3月20日 03:05

恩,看到了。我最近也在用python刷leetcode,遇到大神的博客,感觉收获不少呀。

Avatar_small
kitt 说:
2015年3月20日 19:34

我可不算,大家多交流呗~ 不过我真心觉得Python很简洁 @lhq:


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter