leetcode

commit f96db6a17ac23cf68683f19555c814040a19349f
parent 0a8792642f8a977eadfc9fc66266f46c430ea6a7
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 11 Jul 2023 15:07:45 +0200

Daily Problem

Diffstat:
A
Problems/0863.cpp
 | 
52
++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 53 insertions(+), 0 deletions(-)
diff --git a/Problems/0863.cpp b/Problems/0863.cpp
@@ -0,0 +1,52 @@
+class Solution {
+  TreeNode *parent[501];
+  void find(TreeNode *root, TreeNode *target) {
+    queue<TreeNode *> q({root});
+
+    parent[root->val] = NULL;
+    while (!q.empty()) {
+      for (int k = q.size(); k > 0; k--) {
+        TreeNode *root = q.front();
+        q.pop();
+        if (root == target) return;
+        if (root->left) {
+          parent[root->left->val] = root;
+          q.push(root->left);
+        }
+        if (root->right) {
+          parent[root->right->val] = root;
+          q.push(root->right);
+        }
+      }
+    }
+  }
+
+public:
+  vector<int> distanceK(TreeNode *root, TreeNode *target, int k) {
+    if (k == 0) return {target->val};
+    find(root, target);
+
+    vector<int> res;
+    while (k-- >= 0) {
+      queue<TreeNode *> q({target});
+      for (int i = 0; i <= k && !q.empty(); i++) {
+        for (int t = q.size(); t > 0; t--) {
+          TreeNode *root = q.front();
+          q.pop();
+          if (root->left) q.push(root->left);
+          if (root->right) q.push(root->right);
+        }
+      }
+      while (!q.empty()) {
+        res.push_back(q.front()->val);
+        q.pop();
+      }
+
+      TreeNode *p = parent[target->val];
+      if (!p) break;
+      (p->left == target ? p->left : p->right) = NULL;
+      target = p;
+    }
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -362,6 +362,7 @@ for solving problems.
 |  0851  |   Medium   | [Loud and Rich](Problems/0851.cpp)                                                               |
 |  0853  |   Medium   | [Car Fleet](Problems/0853.cpp)                                                                   |
 |  0859  |    Easy    | [Buddy Strings](Problems/0859.cpp)                                                               |
+|  0863  |   Medium   | [All Nodes Distance K in Binary Tree](Problems/0863.cpp)                                         |
 |  0864  |    Hard    | [Shortest Path to Get All Keys](Problems/0864.cpp)                                               |
 |  0872  |    Easy    | [Leaf-Similar Trees](Problems/0872.cpp)                                                          |
 |  0875  |   Medium   | [Koko Eating Bananas](Problems/0875.cpp)                                                         |