O(n) simple python solution


  • 3
    Y
    class Solution:
    # @param {integer[]} preorder
    # @param {integer[]} inorder
    # @return {TreeNode}
    def buildTree(self, preorder, inorder):
        if not preorder:
            return None
    
        m = {}
        for i in range(0, len(inorder)):
            m[inorder[i]] = i
        return self.construct_bst_help(preorder, 0, len(preorder), m, [0])
    
    
    def construct_bst_help(self, preorder, start, end, m, curr):
        if start == end:
            return None
        if start == end - 1:
            node = TreeNode(preorder[curr[0]])
            curr[0] += 1
            return node
    
        node = TreeNode(preorder[curr[0]])
        curr[0] += 1
        
        i = m[node.val]
        node.left = self.construct_bst_help(preorder, start, i, m, curr)
        node.right = self.construct_bst_help(preorder, i + 1, end, m, curr)
        return node

  • 0
    L

    It is very nice! I came up with a solution similar to the following link by checking the start and end positions of each sub-list, which got many votes, but it only has 300+ms performance in python. I wanted to improve that with dictionary somehow, but I saw this first, which saved me a lot time. Thumbs up for this solution, thanks!

    https://leetcode.com/discuss/18101/sharing-my-straightforward-recursive-solution


  • 0
    L

    I just want to make it easier to read with fewer parameters. Hopefully it can help someone.

    class Solution:
        # @param {integer[]} inorder
        # @param {integer[]} postorder
        # @return {TreeNode}
        def __init__(self):
            self.preorder = []
            self.preorder_index = 0
            self.inorder_indexes = {}
    
        def buildTree(self, preorder, inorder):
            if not preorder:
                return
            self.preorder = preorder
            for i, num in enumerate(inorder):
                self.inorder_indexes[num] = i
            return self._buildTree(0, len(preorder) - 1)
    
        def _buildTree(self, start, end):
            if self.preorder_index == len(self.preorder) or start > end:
                return
            node_val = self.preorder[self.preorder_index]
            node = TreeNode(node_val)
            self.preorder_index += 1
            if start == end:
                return node
            mid = self.inorder_indexes[root_val]
            node.left = self._buildTree(start, mid - 1)
            node.right = self._buildTree(mid + 1, end)
            return node

  • 0
    C

    Nice solution, while the code can be shorten a little bit:

    # O(n)
    def buildTree(self, preorder, inorder):
        if not preorder:
            return None
        dic = {}
        for i, val in enumerate(inorder):
            dic[val] = i
        # the root node index in preorder array
        self.indPre = 0
        return self.help_fun(preorder, 0, len(preorder)-1, dic)
        
    def help_fun(self, preorder, start, end, dic):
        if start > end or self.indPre == len(preorder):
            return None
        root = TreeNode(preorder[self.indPre])
        self.indPre += 1
        index = dic[root.val]
        root.left = self.help_fun(preorder, start, index-1, dic)
        root.right = self.help_fun(preorder, index+1, end, dic)
        return root

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.