C++ short clean solution using BST iterators and two-pointer


  • 0

    Define forward and backward iterators, and then two pointers.

        bool findTarget(TreeNode* r, int k) {
            
            BSTItr LItr(r, true), RItr(r, false);        
            for (auto L = LItr.next(), R = RItr.next(); L && R && L != R;) {
                int sum = L->val + R->val;
                if (sum < k) L = LItr.next();
                else if (sum > k) R = RItr.next();
                else return true;
            }
            return false;
        }
        
        class BSTItr { // BST Iterator class
          private:
            stack<TreeNode*> _s;
            bool _forward; // true if iterating in-order direction
            
            void go2End(TreeNode* r) {
                while (r) {
                    _s.push(r);
                    r = _forward? r->left : r->right;
                }
            }
            
          public:
            BSTItr(TreeNode* r, bool forward):_forward(forward) { go2End(r); }
            
            TreeNode* next() {
                if (_s.empty()) return nullptr;
                auto res = _s.top(); _s.pop();
                go2End(_forward? res->right : res->left);
                return res;
            }
        };
    

Log in to reply
 

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