106. 从中序与后序(前序）遍历序列构造二叉树

作者

106. 从中序与后序遍历序列构造二叉树

  1. class Solution:
  2.     def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
  3.         if not postorder:
  4.             return None
  5.         root_val=postorder[-1]
  6.         root=TreeNode(root_val)
  7.         if len(postorder)==1:
  8.             return root
  9.         left_in=inorder[:inorder.index(root_val)]
  10.         right_in=inorder[inorder.index(root_val)+1:]
  11.         left_post=postorder[:len(left_in)] #!!!
  12.         right_post=postorder[len(left_in):len(postorder)-1] #!!!
  13.         root.left=self.buildTree(left_in,left_post)
  14.         root.right=self.buildTree(right_in,right_post)
  15.         return root
105. 从前序与中序遍历序列构造二叉树

  1. class Solution:
  2.     def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
  3.         if not preorder:
  4.             return None
  5.         root_val=preorder[0]
  6.         root=TreeNode(root_val)
  9.         inorder_left=inorder[:inorder.index(root_val)]
  10.         inorder_right=inorder[inorder.index(root_val)+1:]
  11.         preorder_left=preorder[1:1+len(inorder_left)]
  12.         preorder_right=preorder[1+len(inorder_left):]
  14.         root.left=self.buildTree(preorder_left,inorder_left)
  15.         root.right=self.buildTree(preorder_right,inorder_right)
  16.         return root

注意11,12行区间选择

发表评论