Press "Enter" to skip to content

Posts tagged as “BST”

花花酱 LeetCode 783. Minimum Distance Between BST Nodes

Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.

Example :

Note:

  1. The size of the BST will be between 2 and 100.
  2. The BST is always valid, each node’s value is an integer, and each node’s value is different.

Solution 1: In order traversal 

Time complexity: O(n)

Space complexity: O(n)

C++

Related Problems:

花花酱 LeetCode 315. Count of Smaller Numbers After Self

题目大意:给你一个数组,对于数组中的每个元素,返回一共有多少在它之后的元素比它小。

Problem:

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Return the array [2, 1, 1, 0].

Idea:

Fenwick Tree / Binary Indexed Tree

BST

Solution 1: Binary Indexed Tree (Fenwick Tree)

C++

Java

Solution 2: BST

C++

Java

花花酱 LeetCode 530. Minimum Absolute Difference in BST

Link

Problem:

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Note: There are at least two nodes in this BST.


Idea:

Sorting via inorder traversal gives us sorted values, compare current one with previous one to reduce space complexity from O(n) to O(h).

Solution:

C++ O(n) space

C++ O(h) space

Java

Python

Related Problems:

  • [解题报告] LeetCode 98. Validate Binary Search Tree

花花酱 LeetCode 98. Validate Binary Search Tree

Problem:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

Binary tree [2,1,3], return true.

Example 2:

Binary tree [1,2,3], return false.

Solution 1

Traverse the tree and limit the range of each subtree and check whether root’s value is in the range.

Time complexity: O(n)

Space complexity: O(n)

Note: in order to cover the range of -2^31 ~ 2^31-1, we need to use long or nullable integer.

C++/long

C++/nullable

Java/nullable

Solution 2

Do an in-order traversal, the numbers should be sorted, thus we only need to compare with the previous number.

Time complexity: O(n)

Space complexity: O(n)

C++

Java

Related Problem

花花酱 LeetCode 683. K Empty Slots

题目大意:有n个花盆,第i天,第flowers[i]个花盆的花会开。问是否存在一天,两朵花之间有k个空花盆。

Problem:

There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.

For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.

Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.

If there isn’t such day, output -1.

Example 1:

Input: 
flowers: [1,3,2]
k: 1
Output: 2
Explanation: In the second day, the first and the third flower have become blooming.

Example 2:

Input: 
flowers: [1,2,3]
k: 1
Output: -1

Note:

  1. The given array will be in the range [1, 20000].

Idea:

BST/Buckets



 

Solution 2: BST

C++

Solution 3: Buckets

C++

Solution 1: TLE with latest test cases

C++

Java

Python