106. 从中序与后序遍历序列构造二叉树
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
解法一:递归
和105题类似,区别在于后序的-1号元素是中序的根,划分之后递归
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if len(inorder) == 0 or len(postorder) == 0:
return
root = TreeNode(postorder[-1])
mid = inorder.index(postorder[-1])
#以mid为界划分中序
in_l = inorder[:mid]
in_r = inorder[mid+1:]
#以mid为界划分后序
post_l = postorder[:len(in_l)]
post_r = postorder[len(in_l):-1]
#递归构造左右子树
root.left = self.buildTree(in_l, post_l)
root.right = self.buildTree(in_r, post_r)
return root
最后更新于