leetcode 105.知前序遍历中序遍历求树

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

树

    3
   / \
  9  20
    /  \
   15   7

先构建树

class TreeNode:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None

已知前序遍历第一个值一定是根节点

# root_val = preorder[0]  # 3
root = TreeNode(preorder[0])

找出该值在中序遍历中的index

mid = inorder.index(root) # 1

由中序遍历根结点左边都为左树,右边都为右树知

前序遍历 [3,9,20,15,7]  根  [3]  左树[9] 右树[20,15,7]
中序遍历 [9,3,15,20,7]  左树 [9]  根[3]  右树[15,20,7]

inorder[:mid]  # 左树    
inorder[mid+1:] # 右树    

preorder[1:mid+1] # 左树
preorder[mid+1:] #右树

递归

class Solution:
    def buildTree(self,preorder,inorder):
        if len(inorder) == 0:
            return None
        root = TreeNode(preorder[0])
        mid = inorder.index(root)
        
        root.left = self.buildTree(preorder[1:mid+1],inorder[:mid])
        root.right = self.buildTree(preorder[mid+1:],inorder[mid+1:])
        
        return root