LeetCode 솔루션

[7/14] 105. Construct Binary Tree from Preorder and Inorder Traversal

학부유학생 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.07.13 20:55

6,424 조회
1 댓글
0 추천
0 비추천
목록 게시글 쓰기

105. Construct Binary Tree from Preorder and Inorder Traversal

Medium

9289255Add to ListShare

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.

Accepted

757,048

Submissions

1,289,214

#Microsoft, #Amazon, #Bloomberg, #Adobe, #Google, #Apple, #Uber

링크

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ 2255 회 연결

익명
작성일 2022.07.13 20:58

Runtime: 335 ms, faster than 21.08% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
Memory Usage: 88.7 MB, less than 25.00% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not inorder: return None
        
        root = TreeNode(preorder[0])
        pivot = inorder.index(root.val)
        
        root.left = self.buildTree(preorder[1:pivot+1], inorder[:pivot])
        root.right = self.buildTree(preorder[pivot+1:], inorder[pivot+1:])
      
        return root