Construct Binary Tree from Inorder and Preorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

URL: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if len(inorder) == 1:
            return TreeNode(inorder[0])
        return self.create_tree(inorder, 0, len(inorder) - 1, preorder, 0, len(preorder) - 1)

    def search_divindex(self, inorder, low_inorder, high_inorder, val):
        for i in range(low_inorder, high_inorder+1):
            if inorder[i] == val:
                return i
        return -1

    def create_tree(self, inorder, low_inorder, high_inorder, preorder, low_preorder, high_preorder):
        if (low_preorder > high_preorder) or (low_inorder > high_inorder):
            return None

        root = TreeNode(preorder[low_preorder])
        div_index = self.search_divindex(inorder, low_inorder, high_inorder, root.val)
        size_left_subtree = div_index - low_inorder
        size_right_subtree = high_inorder - div_index

        root.right = self.create_tree(inorder, div_index + 1, high_inorder, preorder, 
                                      low_preorder + 1 + size_left_subtree,
                                      low_preorder + size_left_subtree + size_right_subtree)

        root.left = self.create_tree(inorder, low_inorder, div_index - 1, preorder,
                                     low_preorder + 1, low_preorder + size_left_subtree)

        return root

results matching ""

    No results matching ""