AcWing 18. 重建二叉树(python)
原题链接
中等
作者:
YoloVMe50
,
2023-12-10 14:18:18
,
所有人可见
,
阅读 44
ppy代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
self.hash={}
self.preorder=preorder
self.inorder=inorder
n=len(self.preorder)
for i in range(n):
self.hash[self.inorder[i]]=i
return self.dfs(0,n-1,0,n-1)
def dfs(self,pl,pr,il,ir):
if pl>pr:
return None
root=TreeNode(self.preorder[pl])
k=self.hash[root.val]
left=self.dfs(pl+1,pl-il+k,il,k-1)
right=self.dfs(pl-il+k+1,pr,k+1,ir)
root.left=left
root.right=right
return root