leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0863.cpp (1575B)

      1 class Solution {
      2     TreeNode *parent[501];
      3     void find(TreeNode *root, TreeNode *target) {
      4         queue<TreeNode *> q({root});
      5 
      6         parent[root->val] = NULL;
      7         while (!q.empty()) {
      8             for (int k = q.size(); k > 0; k--) {
      9                 TreeNode *root = q.front();
     10                 q.pop();
     11                 if (root == target) return;
     12                 if (root->left) {
     13                     parent[root->left->val] = root;
     14                     q.push(root->left);
     15                 }
     16                 if (root->right) {
     17                     parent[root->right->val] = root;
     18                     q.push(root->right);
     19                 }
     20             }
     21         }
     22     }
     23 
     24   public:
     25     vector<int> distanceK(TreeNode *root, TreeNode *target, int k) {
     26         if (k == 0) return {target->val};
     27         find(root, target);
     28 
     29         vector<int> res;
     30         while (k-- >= 0) {
     31             queue<TreeNode *> q({target});
     32             for (int i = 0; i <= k && !q.empty(); i++) {
     33                 for (int t = q.size(); t > 0; t--) {
     34                     TreeNode *root = q.front();
     35                     q.pop();
     36                     if (root->left) q.push(root->left);
     37                     if (root->right) q.push(root->right);
     38                 }
     39             }
     40             while (!q.empty()) {
     41                 res.push_back(q.front()->val);
     42                 q.pop();
     43             }
     44 
     45             TreeNode *p = parent[target->val];
     46             if (!p) break;
     47             (p->left == target ? p->left : p->right) = NULL;
     48             target = p;
     49         }
     50         return res;
     51     }
     52 };