commit 913dfac86f8993bcf569db309ab5563e76c6d0e9
parent 811124ffd37639788b10e23a3fbd5afe4e4aabb6
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Fri, 30 Dec 2022 01:20:11 +0100
Binary Search Tree Problems 3
Diffstat:
7 files changed, 215 insertions(+), 0 deletions(-)
diff --git a/Problems/0109.cpp b/Problems/0109.cpp
@@ -0,0 +1,36 @@
+class Solution {
+ struct record {
+ TreeNode *root;
+ ListNode *low, *high;
+ record(TreeNode *root, ListNode *low = nullptr, ListNode *high = nullptr)
+ : root(root), low(low), high(high) {}
+ };
+ ListNode *get_mid(ListNode *list, ListNode *end) {
+ ListNode *slow, *fast;
+ slow = fast = list;
+ while (fast != end && fast->next != end) {
+ fast = fast->next->next;
+ slow = slow->next;
+ }
+ return slow;
+ }
+
+public:
+ TreeNode *sortedListToBST(ListNode *head) {
+ stack<record> st;
+ TreeNode *tree = new TreeNode(INT_MIN), *t;
+ st.push({tree, head, nullptr});
+ while (!st.empty()) {
+ record r = st.top();
+ st.pop();
+ while (r.low != r.high) {
+ ListNode *mid = get_mid(r.low, r.high);
+ (mid->val >= r.root->val ? r.root->right : r.root->left) = t =
+ new TreeNode(mid->val);
+ st.push({r.root = t, mid->next, r.high});
+ r.high = mid;
+ }
+ }
+ return tree->right;
+ }
+};
diff --git a/Problems/0230.cpp b/Problems/0230.cpp
@@ -0,0 +1,17 @@
+class Solution {
+public:
+ int kthSmallest(TreeNode *root, int k) {
+ stack<TreeNode *> st;
+ while (true) {
+ while (root) {
+ st.push(root);
+ root = root->left;
+ }
+ if (st.empty()) break;
+ root = st.top(), st.pop();
+ if (!--k) return root->val;
+ root = root->right;
+ }
+ return -1;
+ }
+};
diff --git a/Problems/1373.cpp b/Problems/1373.cpp
@@ -0,0 +1,48 @@
+class Solution {
+ struct record {
+ int sum, mini, maxi;
+ record(int su = 0, int mi = INT_MAX, int ma = INT_MIN)
+ : sum(su), mini(mi), maxi(ma) {}
+ };
+
+public:
+ int maxSumBST(TreeNode *root) {
+ unordered_map<TreeNode *, record> um;
+ stack<TreeNode *> st;
+
+ int res = 0;
+ st.push(root);
+ while (!st.empty()) {
+ TreeNode *root = st.top();
+ st.pop();
+ if (um.count(root)) {
+ record &r = um[root];
+ if (root->left) {
+ if (root->val <= um[root->left].maxi) {
+ r.mini = INT_MIN, r.maxi = INT_MAX;
+ continue;
+ } else
+ r.sum += um[root->left].sum;
+ }
+
+ if (root->right) {
+ if (root->val >= um[root->right].mini) {
+ r.mini = INT_MIN, r.maxi = INT_MAX;
+ continue;
+ } else
+ r.sum += um[root->right].sum;
+ }
+
+ res = max(res, r.sum);
+ r.mini = root->left ? um[root->left].mini : root->val;
+ r.maxi = root->right ? um[root->right].maxi : root->val;
+ continue;
+ }
+ um.insert({root, root->val});
+ st.push(root);
+ if (root->left) st.push(root->left);
+ if (root->right) st.push(root->right);
+ }
+ return res;
+ }
+};
diff --git a/Problems/1382.cpp b/Problems/1382.cpp
@@ -0,0 +1,44 @@
+class Solution {
+ struct record {
+ TreeNode *root;
+ int low, high;
+ record(TreeNode *root, int low, int high)
+ : root(root), low(low), high(high) {}
+ };
+
+public:
+ TreeNode *balanceBST(TreeNode *root) {
+ vector<TreeNode *> nums;
+
+ {
+ stack<TreeNode *> st;
+ while (true) {
+ while (root) {
+ st.push(root);
+ root = root->left;
+ }
+ if (st.empty()) break;
+ root = st.top(), st.pop();
+ nums.push_back(root);
+ root = root->right;
+ }
+ }
+
+ stack<record> st;
+ TreeNode *head = new TreeNode(INT_MIN), *t;
+ st.push({head, 0, (int)nums.size() - 1});
+ while (!st.empty()) {
+ record r = st.top();
+ st.pop();
+ while (r.low <= r.high) {
+ int mid = r.low + (r.high - r.low) / 2;
+ nums[mid]->left = nums[mid]->right = nullptr;
+ (nums[mid]->val >= r.root->val ? r.root->right : r.root->left) = t =
+ nums[mid];
+ st.push({r.root = t, mid + 1, r.high});
+ r.high = mid - 1;
+ }
+ }
+ return head->right;
+ }
+};
diff --git a/Problems/1834.cpp b/Problems/1834.cpp
@@ -0,0 +1,32 @@
+class Solution {
+ struct item {
+ int index, et, pt;
+ item(int i, int e, int p) : index(i), et(e), pt(p) {}
+ friend bool operator<(const item &i1, const item &i2) {
+ return (i1.pt > i2.pt) || (i1.pt == i2.pt && i1.index > i2.index);
+ }
+ };
+
+public:
+ vector<int> getOrder(vector<vector<int>> &tasks) {
+ vector<item> ss;
+ for (int i = 0; i < tasks.size(); i++)
+ ss.push_back({i, tasks[i][0], tasks[i][1]});
+ sort(ss.begin(), ss.end(),
+ [](const item &i1, const item &i2) { return (i1.et < i2.et); });
+
+ vector<int> res;
+ priority_queue<item> pq;
+ int t = 0;
+ for (int i = 0; i < ss.size();) {
+ if (pq.empty() && t < ss[i].et) t = ss[i].et;
+ while (i < ss.size() && ss[i].et <= t) pq.push(ss[i++]);
+ item it = pq.top();
+ pq.pop();
+ res.push_back(it.index);
+ t += it.pt;
+ }
+ while (!pq.empty()) res.push_back(pq.top().index), pq.pop();
+ return res;
+ }
+};
diff --git a/Problems/1962.cpp b/Problems/1962.cpp
@@ -0,0 +1,32 @@
+// Using a priority_queue
+class Solution {
+public:
+ int minStoneSum(vector<int> &piles, int k) {
+ priority_queue<int> pq;
+ int res = 0;
+ for (int e : piles) res += e, pq.push(e);
+ while (k--) {
+ int t = pq.top(), pq.pop();
+ pq.push(t - t / 2), res -= t / 2;
+ }
+ return res;
+ }
+};
+
+// Using heap, constant memory
+class Solution {
+public:
+ int minStoneSum(vector<int> &piles, int k) {
+ auto b = piles.begin(), e = piles.end();
+ make_heap(b, e);
+ while (k--) {
+ pop_heap(b, e);
+ auto &elem = *(e - 1);
+ elem -= elem / 2;
+ push_heap(b, e);
+ }
+ int sum = 0;
+ for (auto v : piles) sum += v;
+ return sum;
+ }
+};
diff --git a/README.md b/README.md
@@ -47,6 +47,7 @@ if you have any questions.
| 0104 | Easy | [Maximum Depth of Binary Tree](Problems/0104.cpp) |
| 0107 | Medium | [Binary Tree Level Order Traversal II](Problems/0107.cpp) |
| 0108 | Easy | [Convert Sorted Array to Binary Search Tree](Problems/0108.cpp) |
+| 0109 | Medium | [Convert Sorted List to Binary Search Tree](Problems/0109.cpp) |
| 0111 | Easy | [Minimum Depth of Binary Tree](Problems/0111.cpp) |
| 0112 | Easy | [Path Sum](Problems/0112.cpp) |
| 0114 | Medium | [Flatten Binary Tree to Linked List](Problems/0114.cpp) |
@@ -148,6 +149,7 @@ if you have any questions.
| 0783 | Easy | [Minimum Distance Between BST Nodes](Problems/0783.cpp) |
| 0797 | Medium | [All Paths From Source to Target](Problems/0797.cpp) |
| 0802 | Medium | [Find Eventual Safe States](Problems/0802.cpp) |
+| 0830 | Medium | [Kth Smallest Element in a BST](Problems/0230.cpp) |
| 0841 | Medium | [Keys and Rooms](Problems/0841.cpp) |
| 0844 | Easy | [Backspace String Compare](Problems/0844.cpp) |
| 0872 | Easy | [Leaf-Similar Trees](Problems/0872.cpp) |
@@ -189,7 +191,9 @@ if you have any questions.
| 1342 | Easy | [Number of Steps to Reduce a Number to Zero](Problems/1342.cpp) |
| 1346 | Easy | [Check if N and Its Double Exist](Problems/1346.cpp) |
| 1367 | Medium | [Linked List in Binary Tree ](Problems/1367.cpp) |
+| 1373 | Hard | [Maximum Sum BST in Binary Tree](Problems/1373.cpp) |
| 1379 | Easy | [Find a Corresponding Node of a Binary Tree in a Clone of That Tree ](Problems/1379.cpp) |
+| 1382 | Medium | [Balance a Binary Search Tree](Problems/1382.cpp) |
| 1466 | Medium | [Reorder Routes to Make All Paths Lead to the City Zero](Problems/1466.cpp) |
| 1472 | Medium | [Design Browser History ](Problems/1472.cpp) |
| 1480 | Easy | [Running Sum of 1d Array](Problems/1480.cpp) |
@@ -207,7 +211,9 @@ if you have any questions.
| 1706 | Medium | [Where Will the Ball Fall](Problems/1706.cpp) |
| 1791 | Easy | [Find Center of Star Graph](Problems/1791.cpp) |
| 1823 | Medium | [Find the Winner of the Circular Game](Problems/1823.cpp) |
+| 1834 | Medium | [Single-Threaded CPU](Problems/1834.cpp) |
| 1926 | Medium | [Nearest Exit from Entrance in Maze](Problems/1926.cpp) |
+| 1962 | Medium | [Remove Stones to Minimize the Total](Problems/1962.cpp) |
| 1971 | Easy | [Find if Path Exists in Graph](Problems/1971.cpp) |
| 2073 | Easy | [Time Needed to Buy Tickets](Problems/2073.cpp) |
| 2095 | Medium | [Delete the Middle Node of a Linked List](Problems/2095.cpp) |
