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)