This is a place to put my clutters, no matter you like it or not, welcome here.
0%
105. Construct Binary Tree from Preorder and Inorder Traversal
Posted onIn面試Views: Symbols count in article: 1.1kReading time ≈1 mins.
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.
T: O(n), S: O(1) # Definition for a binary tree node. # class TreeNode: # def init(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: # pre : (root, left, right) root is first, find root # in: (left, root, right) construct tree
# Check if the root exist in inorder if len(preorder) and preorder[0] in inorder: # Find the root index in inorer root_index = inorder.index(preorder[0]) # Make the root node tree = TreeNode(preorder[0])
# Build left subtree tree.left = self.buildTree(preorder[1:root_index+1], inorder[:root_index])
# Build right subtree tree.right = self.buildTree(preorder[root_index+1:], inorder[root_index+1:]) return tree