leetcode

commit 647f2b6c7f1403d22bff11ea67fb1e7b7a04e4d4
parent 21316c856a072fb6f21b5c59f24cb65c9fe8060c
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 26 Oct 2024 21:45:59 +0200

1 Random Problem

Diffstat:
A
Problems/2458.cpp
 | 
67
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 68 insertions(+), 0 deletions(-)
diff --git a/Problems/2458.cpp b/Problems/2458.cpp
@@ -0,0 +1,67 @@
+class Solution {
+  public:
+    vector<int> treeQueries(const TreeNode *root, vector<int> &queries) const {
+        static int height[100002];
+        memset(height, 0x00, sizeof(height));
+
+        stack<const TreeNode *> st;
+        st.push(root);
+        while (!st.empty()) {
+            if (st.top() != nullptr) {
+                const auto *root = st.top();
+                st.push(nullptr);
+                if (root->left) st.push(root->left);
+                if (root->right) st.push(root->right);
+                continue;
+            }
+
+            st.pop();
+            const auto *root = st.top();
+            st.pop();
+
+            int &h = height[root->val];
+            if (root->left) h = max(h, height[root->left->val] + 1);
+            if (root->right) h = max(h, height[root->right->val] + 1);
+        }
+
+        queue<const TreeNode *> q;
+        q.push(root);
+        for (int lvl = 0; !q.empty(); lvl++) {
+            int f = 100001, s = 100001;
+
+            queue<const TreeNode *> copy = q;
+            for (int k = size(q); k > 0; k--) {
+                const auto *root = q.front();
+                q.pop();
+                const int val = root->val;
+
+                if (height[val] > height[f])
+                    s = f, f = val;
+                else if (height[val] > height[s])
+                    s = val;
+
+                if (root->left) q.push(root->left);
+                if (root->right) q.push(root->right);
+            }
+
+            if (size(copy) == 1) {
+                height[copy.front()->val] = lvl - 1;
+                continue;
+            }
+
+            const int hf = height[f], hs = height[s];
+            while (!copy.empty()) {
+                const int n = copy.front()->val;
+                copy.pop();
+                if (n != f)
+                    height[n] = hf + lvl;
+                else
+                    height[n] = hs + lvl;
+            }
+        }
+
+        for (auto &n : queries)
+            n = height[n];
+        return queries;
+    }
+};
diff --git a/README.md b/README.md
@@ -1261,6 +1261,7 @@ reference and a base for solving problems.
 |  2444  |    Hard    | [Count Subarrays With Fixed Bounds](Problems/2444.cpp)                                             |
 |  2448  |    Hard    | [Minimum Cost to Make Array Equal](Problems/2448.cpp)                                              |
 |  2452  |   Medium   | [Words Within Two Edits of Dictionary](Problems/2452.cpp)                                          |
+|  2458  |    Hard    | [Height of Binary Tree After Subtree Removal Queries](Problems/2458.cpp)                           |
 |  2461  |   Medium   | [Maximum Sum of Distinct Subarrays With Length K](Problems/2461.cpp)                               |
 |  2462  |   Medium   | [Total Cost to Hire K Workers](Problems/2462.cpp)                                                  |
 |  2465  |    Easy    | [Number of Distinct Averages](Problems/2465.cpp)                                                   |