LeetCode热题100-从前序与中序遍历序列构造二叉树

给定两个整数数组preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入:preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]输出:[3,9,20,null,null,15,7]

思路速记

1. 前序首元素定根
2. 中序劈成左右两半
3. 前序按长度切分对应左右
4. 左右递归建树

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) idx = inorder.index(root_val) root.left = self.buildTree(preorder[1:idx+1], inorder[:idx]) root.right = self.buildTree(preorder[idx+1:], inorder[idx+1:]) return root