有人可以告诉我我的构建二叉树代码哪里做错了吗？

Question

问题要求基于先序和中序数组构建和返回二叉树。我读到了这样一个很好的解决方案：

class Solution:
    def buildTree(self, preorder, inorder):
        if inorder:
            INDEX = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[INDEX])
            root.left = self.buildTree(preorder, inorder[:INDEX])
            root.right = self.buildTree(preorder, inorder[INDEX+1:])
   
            return root

很清晰，也很有用，但是由于索引机制，需要O(n^2)，我想尝试让它更高效。

我尝试制作一张地图以方便索引。这是我尝试过的：

class Solution:
    def buildTree(self, preorder, inorder):
        if not inorder or not preorder:
            return None
        
        inorder_map = {value: index for index, value in enumerate(inorder)}
        
        def buildSubTree(preorder, inorder):
            if not inorder or not preorder:
                return None

            root_value = preorder.pop(0)
            root = TreeNode(root_value)

            root_index = inorder_map[root_value]

            root.left = buildSubTree(preorder, inorder[:root_index])
            root.right = buildSubTree(preorder, inorder[root_index + 1:])
            
            return root
        
        return buildSubTree(preorder, inorder)

但它返回错误答案，一个额外的 NULL。我花了一个小时调试但失败了。

Answer 1

• 你的第二个解决方案仍然是

  O(N ^ 2)

  ，因为

  pop(0)

  本身就是

  O(N)

  。

• 您可以使用

  deque()

  和

  popleft()

  来代替

  pop(0)

  :

• 这是修改后的版本：

from collections import deque


class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def buildTree(self, preorder, inorder):
        preorder = deque(preorder)
        inorder_map = {value: index for index, value in enumerate(inorder)}
        return self._buildTree(preorder, inorder_map, 0, len(inorder) - 1)

    def _buildTree(self, preorder, inorder_map, start, end):
        if start > end:
            return None

        root_value = preorder.popleft()
        root = TreeNode(root_value)
        root_index = inorder_map[root_value]

        root.left = self._buildTree(preorder, inorder_map, start, root_index - 1)
        root.right = self._buildTree(preorder, inorder_map, root_index + 1, end)

        return root


def test_buildTree():
    solution = Solution()

    preorder = [3, 9, 20, 15, 7]
    inorder = [9, 3, 15, 20, 7]
    root = solution.buildTree(preorder, inorder)

    assert root.val == 3
    assert root.left.val == 9
    assert root.right.val == 20
    assert root.right.left.val == 15
    assert root.right.right.val == 7

    print("Test passed.")


test_buildTree()

打印

Test passed.