動機

把105改一下

Problem

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

 

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]Output: [3,9,20,null,null,15,7]

Example 2:

Input: inorder = [-1], postorder = [-1]Output: [-1]

 

Constraints:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder and postorder consist of unique values.
  • Each value of postorder also appears in inorder.
  • inorder is guaranteed to be the inorder traversal of the tree.
  • postorder is guaranteed to be the postorder traversal of the tree.

Sol

把105改一下

class Solution:
    def buildTree(self, ino: List[int], pos: List[int]) -> TreeNode:
        if not ino or not pos:
            return None
        elif pos[-1] in ino:
            i = ino.index(pos[-1])
            ret = TreeNode(pos[-1])
            ret.left, ret.right = [self.buildTree(ino[:i],pos[:-1]), self.buildTree(ino[i+1:],pos[:-1])]
            return ret
        else:
            return self.buildTree(ino,pos[:-1])