花花酱 LeetCode 1305. All Elements in Two Binary Search Trees

By zxi on December 29, 2019

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]

Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]

Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]

Example 5:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

Constraints:

Each tree has at most 5000 nodes.
Each node’s value is between [-10^5, 10^5].

Solution: Inorder traversal + Merge Sort

Time complexity: O(t1 + t2)
Space complexity: O(t1 + t2)

C++

// Author: Huahua

class Solution {

public:

vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {

function<void(TreeNode*, vector<int>&)> inorder = [&](TreeNode* root, vector<int>& t) {

if (!root) return;

inorder(root->left, t);

t.push_back(root->val);

inorder(root->right, t);

};

vector<int> t1;

vector<int> t2;

inorder(root1, t1);

inorder(root2, t2);

vector<int> m;

int i = 0;

int j = 0;

while (m.size() != t1.size() + t2.size()) {

if (j == t2.size()) m.push_back(t1[i++]);

else if (i == t1.size()) m.push_back(t2[j++]);

else m.push_back(t1[i] < t2[j] ? t1[i++] : t2[j++]);

}

return m;

}

};

C++/STL

// Author: Huahua

class Solution {

public:

vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {

function<void(TreeNode*, vector<int>&)> inorder = [&](TreeNode* root, vector<int>& t) {

if (!root) return;

inorder(root->left, t);

t.push_back(root->val);

inorder(root->right, t);

};

vector<int> t1;

vector<int> t2;

inorder(root1, t1);

inorder(root2, t2);

vector<int> m;

std::merge(begin(t1), end(t1), begin(t2), end(t2), back_inserter(m));

return m;

}

};

花花酱 LeetCode 1296. Divide Array in Sets of K Consecutive Numbers

By zxi on December 26, 2019

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into sets of k consecutive numbers
Return True if its possibleotherwise return False.

Example 1:

Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].

Example 2:

Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
Output: true
Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].

Example 3:

Input: nums = [3,3,2,2,1,1], k = 3
Output: true

Example 4:

Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= nums.length

Solution: BST + Greedy

Start from the smallest available number and find k consecutive numbers.

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool isPossibleDivide(vector<int>& nums, int k) {

if (nums.size() % k) return false;

map<int, int> m;

for (int num : nums) ++m[num];

while (m.size()) {

const int s = m.cbegin()->first;

for (int i = 0; i < k; ++i) {

auto it = m.find(s + i);

if (it == m.cend()) return false;

if (--it->second == 0) m.erase(it);

}

return true;

}

};

C++/V2

// Author: Huahua

class Solution {

public:

bool isPossibleDivide(vector<int>& nums, int k) {

if (nums.size() % k) return false;

map<int, int> m;

for (int num : nums) ++m[num];

while (m.size()) {

auto it = m.begin();

const int s = it->first;

for (int i = 0; i < k; ++i, ++it) {

if (it->first != s + i) return false;

if (--it->second == 0) m.erase(it);

}

return true;

}

};

Solution 2: HashTable

Time complexity: O(n)
Space complexity: O(n)

C++

class Solution {

public:

bool isPossibleDivide(vector<int>& nums, int k) {

if (nums.size() % k) return false;

unordered_map<int, int> m;

for (int num : nums) ++m[num];

queue<int> starts;

for (auto [n, f] : m)

if (!m.count(n - 1)) starts.push(n);

while (!starts.empty()) {

int s = starts.front();

starts.pop();

for (int t = s + k - 1; t >= s; t--) {

if (m[t] < m[s]) return false;

if ((m[t] -= m[s]) == 0) {

m.erase(t);

if (m.count(t + 1)) starts.push(t + 1);

}

return true;

}

};

花花酱 LeetCode 230. Kth Smallest Element in a BST

By zxi on April 13, 2019

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Example 1:

Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
Output: 3

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Solution: Inorder traversal

Time complexity: O(n)
Space compleixty: O(n)

C++

class Solution {

public:

int kthSmallest(TreeNode* root, int k) {

return inorder(root, k);

}

private:

int inorder(TreeNode* root, int& k) {

if (!root) return -1;

int x = inorder(root->left, k);

if (k == 0) return x;

if (--k == 0) return root->val;

return inorder(root->right, k);

}

};

花花酱 LeetCode Binary Trees 二叉树 SP12

By zxi on December 16, 2018

Binary tree is one of the most frequently asked question type during interview.

二叉树是面试中经常会问到的问题。

The candidate needs to understand the recursively defined TreeNode and solve the problem through recursion.

面试者需要理解递归定义的TreeNode数据类型，并且通过使用递归的方式来解决问题。

花花酱 LeetCode 938. Range Sum of BST

By zxi on November 10, 2018

Problem

Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).

The binary search tree is guaranteed to have unique values.

Example 1:

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23

Note:

The number of nodes in the tree is at most 10000.
The final answer is guaranteed to be less than 2^31.

Solution: In-order traversal

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, running time: 72 ms

class Solution {

public:

int rangeSumBST(TreeNode* root, int L, int R) {

if (!root) return 0;

int sum = 0;

if (root->val >= L) sum += rangeSumBST(root->left, L, R);

if (root->val >= L && root->val <= R) sum += root->val;

if (root->val <= R) sum += rangeSumBST(root->right, L, R);

return sum;

}

};

Posts tagged as “BST”

花花酱 LeetCode 1305. All Elements in Two Binary Search Trees

Solution: Inorder traversal + Merge Sort

C++

C++/STL

花花酱 LeetCode 1296. Divide Array in Sets of K Consecutive Numbers

Solution: BST + Greedy

C++

C++/V2

Solution 2: HashTable

C++

Related Problems

花花酱 LeetCode 230. Kth Smallest Element in a BST

C++

花花酱 LeetCode Binary Trees 二叉树 SP12

花花酱 LeetCode 938. Range Sum of BST

Problem

Solution: In-order traversal

C++