给定二叉搜索树的插入顺序求深度

Submission

运行时间: 2055 ms

内存: 39.4 MB

from sortedcontainers import SortedList

class Solution:
    def maxDepthBST(self, order: List[int]) -> int:
        book = defaultdict(int)
        sl = SortedList([0])
        ans = 0
        for x in order:
            k = sl[sl.bisect_left(x) - 1]
            book[x + 1] = book[k + 1] = book[k + 1] + 1
            sl.add(x)
            if ans < book[k + 1]: ans = book[k + 1]
        return ans

Explain

该题解使用了一个平衡二叉树（通过SortedList实现）和一个哈希表（defaultdict）来跟踪插入的每个元素的深度。对于输入的每一个元素x，我们首先查找它应该插入的位置。在SortedList中，我们找到紧邻x左侧的元素k，并将x的深度设置为k的深度加1。每次插入后，我们将x添加到SortedList中以保持元素的有序性，并更新最大深度。通过这种方式，我们可以有效地计算出二叉搜索树的最大深度。

时间复杂度: O(n log n)

空间复杂度: O(n)

from sortedcontainers import SortedList
from collections import defaultdict

class Solution:
    def maxDepthBST(self, order: List[int]) -> int:
        book = defaultdict(int)  # 用于存储每个节点的深度
        sl = SortedList([0])  # 初始化SortedList，用于维护元素的排序顺序
        ans = 0  # 用于记录最大深度
        for x in order:  # 遍历插入序列
            k = sl[sl.bisect_left(x) - 1]  # 找到x左侧的元素
            book[x + 1] = book[k + 1] = book[k + 1] + 1  # 更新x的深度为k的深度加1
            sl.add(x)  # 将x加入到SortedList中，保持排序
            if ans < book[k + 1]: ans = book[k + 1]  # 更新最大深度
        return ans  # 返回最大深度

Explore

SortedList是一种自动维护元素排序的数据结构，使用简单且在某些编程语言和库中直接可用，如Python的sortedcontainers库。它通过一种平衡树结构（通常是红黑树或AVL树）实现，提供了高效的插入、删除和查找操作。选择SortedList而非直接使用AVL或红黑树，主要是因为SortedList提供了更简洁的API和较少的实现复杂度，同时保持了较好的性能，尤其是在需要频繁进行有序操作的场景下。

在提到的代码实现中，使用`sl[sl.bisect_left(x) - 1]`来找到x左侧的元素k。如果x小于SortedList中的所有元素，`sl.bisect_left(x)`将返回0，此时`sl[sl.bisect_left(x) - 1]`会变为`sl[-1]`，即列表中的最后一个元素，这在逻辑上是不正确的。正确的处理方式应当是检查`sl.bisect_left(x)`的值是否为0，如果为0，则表示没有左侧元素，x的深度应该是1，因为它将作为树的根节点或其子树的根节点。

确实，`book[x + 1] = book[k + 1] = book[k + 1] + 1`这行代码存在逻辑和可能的语法错误。正确的方式应该是首先计算新的深度值，然后更新x对应的深度。例如，先通过`new_depth = book[k] + 1`计算出新的深度，然后使用`book[x] = new_depth`来更新x的深度。这样可以避免混淆和错误的数据更新。