O(n) Solution


  • 0
    L

    ...
    /**

    • Definition for a binary tree node.

    • struct TreeNode {

    • int val;
      
    • TreeNode *left;
      
    • TreeNode *right;
      
    • TreeNode(int x) : val(x), left(NULL), right(NULL) {}
      
    • };
      */
      class Solution {
      public:

      TreeNode* getPredecessor(TreeNode* node, stack<TreeNode*>& Pre)
      {
      if(node&&node->left)
      {
      node = node->left;
      while(node&&node->right!=nullptr){ Pre.push(node); node=node->right; }
      return node;
      }
      else
      {
      node = nullptr;
      if(Pre.size()) {node = Pre.top(); Pre.pop();}
      return node;
      }
      }

      TreeNode* getSuccessor(TreeNode* node, stack<TreeNode*>& Suc)
      {
      if(node&&node->right)
      {
      node = node->right;
      while(node&&node->left!=nullptr){ Suc.push(node); node=node->left;}
      return node;
      }
      else
      {
      node = nullptr;
      if(Suc.size()){node = Suc.top(); Suc.pop();}
      return node;
      }
      }

      vector<int> closestKValues(TreeNode* root, double target, int k) {

       vector<int> result;
       if(root==nullptr||k==0)
           return result;
           
       stack<TreeNode*> Pre;
       stack<TreeNode*> Suc;
       TreeNode *node = root;
           
       while(node!=nullptr)
       {
           if(node->val<=target){Pre.push(node); node = node->right;}
           else if(node->val>target){Suc.push(node);node = node->left;}
       }
       TreeNode* pre =  getPredecessor(nullptr,Pre);
       TreeNode* suc =  getSuccessor(nullptr,Suc);    
       while(result.size()<k)
       {
           if(pre&&suc)
           {   
               if( target - pre->val >= suc->val - target ){  result.push_back(suc->val); suc = getSuccessor(suc,Suc); }
               else{ result.push_back(pre->val); pre = getPredecessor(pre,Pre); }
           }
           else if(suc==nullptr)   {  result.push_back(pre->val); pre = getPredecessor(pre,Pre);}
           else                    {  result.push_back(suc->val); suc = getSuccessor(suc,Suc);}
       }
       return result;
      

      }
      };
      ...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.