README_EN.md

1902. Depth of BST Given Insertion Order

中文文档

Description

You are given a 0-indexed integer array order of length n, a permutation of integers from 1 to n representing the order of insertion into a binary search tree.

A binary search tree is defined as follows:

<li>The left subtree of a node contains only nodes with keys <strong>less than</strong> the node&#39;s key.</li>

<li>The right subtree of a node contains only nodes with keys <strong>greater than</strong> the node&#39;s key.</li>

<li>Both the left and right subtrees must also be binary search trees.</li>

The binary search tree is constructed as follows:

<li><code>order[0]</code> will be the <strong>root</strong> of the binary search tree.</li>

<li>All subsequent elements are inserted as the <strong>child</strong> of <strong>any</strong> existing node such that the binary search tree properties hold.</li>

Return the depth of the binary search tree.

A binary tree's depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

 

Example 1:

Input: order = [2,1,4,3]

Output: 3

Explanation: The binary search tree has a depth of 3 with path 2->3->4.

Example 2:

Input: order = [2,1,3,4]

Output: 3

Explanation: The binary search tree has a depth of 3 with path 2->3->4.

Example 3:

Input: order = [1,2,3,4]

Output: 4

Explanation: The binary search tree has a depth of 4 with path 1->2->3->4.

 

Constraints:

<li><code>n == order.length</code></li>

<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>

<li><code>order</code> is a permutation of integers between <code>1</code> and <code>n</code>.</li>

Solutions

Python3

from sortedcontainers import SortedDict


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

Java

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;
    }
}

...