1. 题目
给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
提示:
1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
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, inorder: List[int], postorder: List[int]) -> TreeNode:
if not inorder and not postorder:
return None
root_val = postorder[len(postorder) - 1]
root = TreeNode(root_val)
i = inorder.index(root_val) # i = 1
root.left = self.buildTree(inorder[: i], postorder[: i])
root.right = self.buildTree(inorder[i + 1:], postorder[i: -1])
return