An easy Python solution


  • 25
    G

    The idea is to find the root first, then recursively build each left and right subtree

    # Definition for a  binary tree node
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        # @param num, a list of integers
        # @return a tree node
        # 12:37
        def sortedArrayToBST(self, num):
            if not num:
                return None
    
            mid = len(num) // 2
    
            root = TreeNode(num[mid])
            root.left = self.sortedArrayToBST(num[:mid])
            root.right = self.sortedArrayToBST(num[mid+1:])
    
            return root

  • 2
    L

    Hello, maybe this is not perfect place to ask this question. But I am very curious whether we are allowed use a copy of lists in these recursive functions in the interview (num[:mid] and num[mid+1:] are actually creating extra sublists). It works for this problem well but for problems like ConstructBinaryTreeFromPreorderAndInoderTraversal, when I used similar method which is very straightforwad , it works locally but OJ gives memory limit exceed. Later I solved it by dealing with indexes instead of passing copy of lists(300+ms) and improved it with the help of hash table(70+ms) but it took me long time. I hope to use the first solution if possible since we don't have much time.

    class Solution:
        # @param {integer[]} preorder
        # @param {integer[]} inorder
        # @return {TreeNode}
        def buildTree(self, preorder, inorder):
            if not preorder:
                return
            root = TreeNode(preorder[0])
            self._buildTree(preorder, inorder, root)
            return root
    
        def _buildTree(self, preorder, inorder, root):
            if not preorder:
                return
            for i, num in enumerate(inorder):
                if root.val == num:
                    break
            if i != 0:
                root.left = TreeNode(preorder[1])
                self._buildTree(preorder[1:i+1], inorder[:i], root.left)
            if i != len(preorder) - 1:
                root.right = TreeNode(preorder[i+1])
                self._buildTree(preorder[i+1:], inorder[i+1:], root.right)
            
    class Solution:
        # @param {integer[]} preorder
        # @param {integer[]} inorder
        # @return {TreeNode}
        def buildTree(self, preorder, inorder):
            if not preorder:
                return
            return self._buildTree(preorder, inorder, 0, len(preorder) - 1, 0, len(inorder) - 1)
    
        def _buildTree(self, preorder, inorder, pre_start, pre_end, in_start, in_end):
            if pre_start > pre_end:
                return
            root = TreeNode(preorder[pre_start])
            for i in range(in_start, in_end + 1):
                if root.val == inorder[i]:
                    break
            if in_start != i:
                root.left = self._buildTree(preorder, inorder, pre_start + 1, pre_start + i - in_start, in_start, i - 1)
            if in_end != i:
                root.right = self._buildTree(preorder, inorder, pre_start + i - in_start + 1, pre_end, i + 1, in_end)
            return root
    
    class Solution:
        # @param {integer[]} preorder
        # @param {integer[]} inorder
        # @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
            root_val = self.preorder[self.preorder_index]
            node = TreeNode(root_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
    G

    You don't necessary need to slice and make a copy of the preOrder

    # Definition for a  binary tree node
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        # @param preorder, a list of integers
        # @param inorder, a list of integers
        # @return a tree node
        # 1:59
        def buildTree(self, preorder, inorder):
            if not preorder or not inorder:
                return None
    
            rootValue = preorder.pop(0)
            root = TreeNode(rootValue)
            inorderIndex = inorder.index(rootValue)
    
            root.left = self.buildTree(preorder, inorder[:inorderIndex])
            root.right = self.buildTree(preorder, inorder[inorderIndex+1:])
    
            return root

  • 0
    L

    Are you not creating new lists by calling inorder[:inorderIndex] and inorder[inorderIndex+1:]? It takes around 300ms. However, I think I will use this solution in a interview since it's easy to write. Btw, I tried to do it in your way and ended up with the following solution similar to yours but slicing preorder instead of inorder :)

    def buildTree(self, preorder, inorder):
        if not preorder:
            return
        val = preorder[0]
        root = TreeNode(val)
        i = inorder.index(val)
        inorder.remove(val)
        root.left = self.buildTree(preorder[1:i+1], inorder)
        root.right = self.buildTree(preorder[i+1:], inorder)
        return root

  • 1
    S

    If you try [0,1] you will return [1,0] rather than the expected [0,null,1], although the answer is also accepted.
    So I would suggest to set mid = len(nums)//2 if len(nums)%2 != 0 else len(nums)//2 - 1


  • 1
    M

    In my opinion, to meet the problem's requirement, we just need to change "mid = len(nums) // 2" to "mid = (len(nums) - 1) // 2"


  • 0
    I

    @Google my solution as well. But when I test
    [1, 2, 3, 4, 5, 6, 7, 12, 24, 125]
    it doesn't give the same result as expected. And this is just a random list I typed to replace the empty list template.
    0_1492485126629_Capture.PNG


  • 0
    L

    @swengzju Thank you for letting me know that the answer would be accepted. I wrote the same codes and I did customized testing, I was scared by the result. I literally don't know how to general that "null" in Python.


Log in to reply
 

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