给定两个整数数组 preorder
和 inorder
,其中 preorder
是二叉树的先序遍历, inorder
是同一棵树的中序遍历,请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1] 输出: [-1]
- # Definition for a binary tree node.
- # class TreeNode:
- # def __init__(self, val=0, left=None, right=None):
- # self.val = val
- # self.left = left
- # self.right = right
- class Solution:
- def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
- if not preorder or not inorder:
- return None
- root_val=preorder[0]
- root=TreeNode(root_val)
-
- root_inorder_index=inorder.index(root_val)
-
- inorder_left=inorder[:root_inorder_index]
- inorder_right=inorder[root_inorder_index+1:]
-
- preorder_left=preorder[1:len(inorder_left)+1]
- preorder_right=preorder[len(inorder_left)+1:]
-
- root.left=self.buildTree(preorder_left,inorder_left)
- root.right=self.buildTree(preorder_right,inorder_right)
-
- return root