動機

複習inorder與preorder

可以順便看106

Problem

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

 

Example 1:

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

Example 2:

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

 

Constraints:

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

Sol

python的list slice好讚

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