AcWing 18. 【python-递归】重建二叉树
原题链接
中等
作者:
crunch
,
2022-02-26 09:22:41
,
所有人可见
,
阅读 165
【python-递归】重建二叉树
代码
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def __repr__(self):
return str(self.val)
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if len(preorder) == 0:
return
val = preorder[0]
root = TreeNode(val)
i_id = inorder.index(val)
left = self.buildTree(preorder[1:1+i_id], inorder[:i_id])
right = self.buildTree(preorder[1+i_id:], inorder[i_id+1:])
root.left = left
root.right = right
return root
if __name__ =='__main__':
sol = Solution()
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
print(sol.buildTree(preorder, inorder))