construct_binary_tree_from_preorder_and_inorder_traversal
1from utils import TreeNode 2from typing import Optional 3 4 5# @leet start 6class Solution: 7 def buildTree(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]: 8 """ 9 This question asks us to construct a binary tree from a preorder and 10 inorder traversal. To do so, we note that the first item in a preorder 11 traversal is always the root of the current tree, so we can make our root 12 with `preorder[0]`. 13 14 To find the left side of the tree, we find the index of `preorder[0]` 15 in the inorder array, because that cuts the left and right subtrees. 16 So, to build the left of the current tree, we can recursively pass 17 `preorder[1:i + 1]` and `inorder[:i]`, which passes the left sides of 18 the preorder and inorder arrays to `buildTree` and set that as our 19 left side. 20 21 We do the same for the right side, which is `preorder[i + 1:]`, and 22 `inorder[i+1:]`. 23 24 This solution is $O(n^2)$ time, and a faster solution would require 25 putting all the indexes in a hashmap for constant time access to find 26 the index. 27 """ 28 return self.faster(preorder, inorder) 29 30 def simple(self, preorder, inorder): 31 if not preorder or not inorder: 32 return None 33 34 root = TreeNode(preorder[0]) 35 i = inorder.index(preorder[0]) 36 root.left = self.buildTree(preorder[1 : i + 1], inorder[:i]) 37 root.right = self.buildTree(preorder[i + 1 :], inorder[i + 1 :]) 38 39 return root 40 41 def faster(self, preorder, inorder): 42 def array_to_tree(left, right): 43 nonlocal preorder_index 44 if left > right: 45 return None 46 47 root_value = preorder[preorder_index] 48 root = TreeNode(root_value) 49 50 preorder_index += 1 51 52 root.left = array_to_tree(left, inorder_index_map[root_value] - 1) 53 root.right = array_to_tree(inorder_index_map[root_value] + 1, right) 54 55 return root 56 57 preorder_index = 0 58 59 inorder_index_map = {num: i for i, num in enumerate(inorder)} 60 61 return array_to_tree(0, len(preorder) - 1) 62 63 64# @leet end 65 66 67def test(): 68 assert 2 + 2 == 4
class
Solution:
7class Solution: 8 def buildTree(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]: 9 """ 10 This question asks us to construct a binary tree from a preorder and 11 inorder traversal. To do so, we note that the first item in a preorder 12 traversal is always the root of the current tree, so we can make our root 13 with `preorder[0]`. 14 15 To find the left side of the tree, we find the index of `preorder[0]` 16 in the inorder array, because that cuts the left and right subtrees. 17 So, to build the left of the current tree, we can recursively pass 18 `preorder[1:i + 1]` and `inorder[:i]`, which passes the left sides of 19 the preorder and inorder arrays to `buildTree` and set that as our 20 left side. 21 22 We do the same for the right side, which is `preorder[i + 1:]`, and 23 `inorder[i+1:]`. 24 25 This solution is $O(n^2)$ time, and a faster solution would require 26 putting all the indexes in a hashmap for constant time access to find 27 the index. 28 """ 29 return self.faster(preorder, inorder) 30 31 def simple(self, preorder, inorder): 32 if not preorder or not inorder: 33 return None 34 35 root = TreeNode(preorder[0]) 36 i = inorder.index(preorder[0]) 37 root.left = self.buildTree(preorder[1 : i + 1], inorder[:i]) 38 root.right = self.buildTree(preorder[i + 1 :], inorder[i + 1 :]) 39 40 return root 41 42 def faster(self, preorder, inorder): 43 def array_to_tree(left, right): 44 nonlocal preorder_index 45 if left > right: 46 return None 47 48 root_value = preorder[preorder_index] 49 root = TreeNode(root_value) 50 51 preorder_index += 1 52 53 root.left = array_to_tree(left, inorder_index_map[root_value] - 1) 54 root.right = array_to_tree(inorder_index_map[root_value] + 1, right) 55 56 return root 57 58 preorder_index = 0 59 60 inorder_index_map = {num: i for i, num in enumerate(inorder)} 61 62 return array_to_tree(0, len(preorder) - 1)
8 def buildTree(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]: 9 """ 10 This question asks us to construct a binary tree from a preorder and 11 inorder traversal. To do so, we note that the first item in a preorder 12 traversal is always the root of the current tree, so we can make our root 13 with `preorder[0]`. 14 15 To find the left side of the tree, we find the index of `preorder[0]` 16 in the inorder array, because that cuts the left and right subtrees. 17 So, to build the left of the current tree, we can recursively pass 18 `preorder[1:i + 1]` and `inorder[:i]`, which passes the left sides of 19 the preorder and inorder arrays to `buildTree` and set that as our 20 left side. 21 22 We do the same for the right side, which is `preorder[i + 1:]`, and 23 `inorder[i+1:]`. 24 25 This solution is $O(n^2)$ time, and a faster solution would require 26 putting all the indexes in a hashmap for constant time access to find 27 the index. 28 """ 29 return self.faster(preorder, inorder)
This question asks us to construct a binary tree from a preorder and
inorder traversal. To do so, we note that the first item in a preorder
traversal is always the root of the current tree, so we can make our root
with preorder[0].
To find the left side of the tree, we find the index of preorder[0]
in the inorder array, because that cuts the left and right subtrees.
So, to build the left of the current tree, we can recursively pass
preorder[1:i + 1] and inorder[:i], which passes the left sides of
the preorder and inorder arrays to buildTree and set that as our
left side.
We do the same for the right side, which is preorder[i + 1:], and
inorder[i+1:].
This solution is $O(n^2)$ time, and a faster solution would require putting all the indexes in a hashmap for constant time access to find the index.
def
simple(self, preorder, inorder):
31 def simple(self, preorder, inorder): 32 if not preorder or not inorder: 33 return None 34 35 root = TreeNode(preorder[0]) 36 i = inorder.index(preorder[0]) 37 root.left = self.buildTree(preorder[1 : i + 1], inorder[:i]) 38 root.right = self.buildTree(preorder[i + 1 :], inorder[i + 1 :]) 39 40 return root
def
faster(self, preorder, inorder):
42 def faster(self, preorder, inorder): 43 def array_to_tree(left, right): 44 nonlocal preorder_index 45 if left > right: 46 return None 47 48 root_value = preorder[preorder_index] 49 root = TreeNode(root_value) 50 51 preorder_index += 1 52 53 root.left = array_to_tree(left, inorder_index_map[root_value] - 1) 54 root.right = array_to_tree(inorder_index_map[root_value] + 1, right) 55 56 return root 57 58 preorder_index = 0 59 60 inorder_index_map = {num: i for i, num in enumerate(inorder)} 61 62 return array_to_tree(0, len(preorder) - 1)
def
test():