1. 题目
给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。
2. 题解
from typing import List
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]) -> TreeNode:
if not preorder and not inorder:
return None
root = TreeNode(preorder[0])
i = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1: i+1], inorder[: i])
root.right = self.buildTree(preorder[i + 1:], inorder[i + 1:])
return root
if __name__ == "__main__":
s = Solution()
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
s.buildTree(preorder, inorder)