跳转至

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

题目描述

给定一个从 0 开始索引的整数类型数组 order ，其长度为 n，是从 1 到 n 的所有整数的一个排列，表示插入到一棵二叉搜索树的顺序。

二叉搜索树的定义如下：

  • 一个节点的左子树只包含键值小于该节点键值的节点。
  • 一个节点的右子树只包含键值大于该节点键值的节点。
  • 左子树和右子树须均为二叉搜索树。

该二叉搜索树的构造方式如下：

  • order[0] 将成为该二叉搜索树的根。
  • 所有后续的元素均在维持二叉搜索树性质的前提下作为任何已存在节点的子节点插入。

返回该二叉搜索树的深度。

一棵二叉树的深度是从根节点到最远叶节点的最长路径所经节点的个数。

 

示例 1:

输入: order = [2,1,4,3]
输出: 3
解释: 该二叉搜索树的深度为 3，路径为 2->4->3。

示例 2:

输入: order = [2,1,3,4]
输出: 3
解释: 该二叉搜索树的深度为 3，路径为 2->3->4。

示例 3:

输入: order = [1,2,3,4]
输出: 4
解释: 该二叉搜索树的深度为 4，路径为 1->2->3->4。

 

提示：

  • n == order.length
  • 1 <= n <= 105
  • order 是从 1 到 n 的整数的一个排列。

解法

方法一

思考

按插入顺序模拟建树，每次从根下降到空位，单次为 \(O(n)\)，总时间 \(O(n^2)\)。\(n\le 10^5\) 时不可行。

新结点在 BST 中必挂在已插入值中最邻近的前驱或后继之下，深度等于二者深度的较大值加一。因此不必维护指针，只需在有序序列中查询邻居深度。

为此用有序字典保存已插入值及其深度，哨兵 \(0\) 与 \(+\infty\) 保证两端有邻居。对每个 \(v\) 二分定位前驱、后继，写入新深度并更新全局最大值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maxDepthBST(self, order: List[int]) -> int:
        sd = SortedDict({0: 0, inf: 0, order[0]: 1})
        ans = 1
        for v in order[1:]:
            lower = sd.bisect_left(v) - 1
            higher = lower + 1
            depth = 1 + max(sd.values()[lower], sd.values()[higher])
            ans = max(ans, depth)
            sd[v] = depth
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxDepthBST(int[] order) {
        TreeMap<Integer, Integer> tm = new TreeMap<>();
        tm.put(0, 0);
        tm.put(Integer.MAX_VALUE, 0);
        tm.put(order[0], 1);
        int ans = 1;
        for (int i = 1; i < order.length; ++i) {
            int v = order[i];
            Map.Entry<Integer, Integer> lower = tm.lowerEntry(v);
            Map.Entry<Integer, Integer> higher = tm.higherEntry(v);
            int depth = 1 + Math.max(lower.getValue(), higher.getValue());
            ans = Math.max(ans, depth);
            tm.put(v, depth);
        }
        return ans;
    }
}

评论