给出二叉树的先序和后序遍历,构建二叉树,数据结构基础题,看Discussion学到了一边处理后序序列一边pop掉已经处理的元素,写法更简洁
1 #106
2 #Runtime: 110 ms (Beats 55.7%)
3 #Memory: 52.3 MB (Beats 49.76%)
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def buildTree(self, inorder, postorder):
13 """
14 :type inorder: List[int]
15 :type postorder: List[int]
16 :rtype: TreeNode
17 """
18 if not inorder:
19 return None
20 root = TreeNode(postorder.pop())
21 idx = inorder.index(root.val)
22 root.right = self.buildTree(inorder[idx + 1 : ], postorder)
23 root.left = self.buildTree(inorder[ : idx], postorder)
24 return root