653. Two Sum IV - Input is a BST

Problem description: https://leetcode.com/problems/two-sum-iv-input-is-a-bst/description/
Solution 1: Conduct two in-order searches from left most and right most leaves. (fastest)
    bool findTarget(TreeNode* root, int k) {
        if(!root) return false;
        TreeNode* nl = root, * nh = root, *nle, *nhe;
        stack<TreeNode*> stl, sth;
        while(nl) {stl.push(nl); nl = nl->left; }
        while(nh) {sth.push(nh); nh = nh->right; }
        nle = stl.top();
        nhe = sth.top();
        int lo = nle->val, hi = nhe->val;
        while(nle != nhe) {
            if(lo + hi == k) return true;
            if(lo + hi < k) {
                while(nl) {stl.push(nl); nl = nl->left;}
                nle = stl.top();
                stl.pop();
                lo = nle->val;
                nl = nle->right;
            }
            else {
                while(nh) {sth.push(nh); nh = nh->right;}
                nhe = sth.top();
                sth.pop();
                hi = nhe->val;
                nh = nhe->left;
            }
        }
        return false;
    }
Solution 2:
Make an in-order traversal for the BST and get the values in an array in ascending order. Then do the two sum of O(n).
    void inOrder(TreeNode* node, vector<int>& vt){
        if(!node) return;
        if(node->left)
            inOrder(node->left, vt);
        vt.push_back(node->val);
        if(node->right)
            inOrder(node->right, vt);
    }
    bool findTarget(TreeNode* root, int k) {
        vector<int> vt;
        inOrder(root,vt);
        for(int i=0, j=vt.size()-1;i<j;){
            if(vt[i]+vt[j] == k) return true;
            else if(vt[i]+vt[j]>k) j--;
            else i++;
        }
        return false;
    }
Solution 3:
Construct iterator objects for the tree.
    class BSTiterator{
        private:
            stack<TreeNode*> s;
            TreeNode* node;
            bool inc;
        public:
            BSTiterator(TreeNode*root, bool increase):node(root),inc(increase){}
            int next(){
                while(!s.empty()||node) {
                    if(node) {
                        s.push(node);
                        node = inc ? node->left:node->right;
                    }
                    else {
                        node = s.top();
                        s.pop();
                        int nval = node->val;
                        node = inc ? node->right:node->left;
                        return nval;
                    }
                }
                return -1;
            }
    };
    bool findTarget(TreeNode* root, int k) {
        if(!root) return false;
        BSTiterator f(root,true);
        BSTiterator b(root,false);
        for(int i=f.next(), j=b.next();i<j;){
            if(i+j == k) return true;
            else if(i+j<k) i = f.next();
            else j = b.next();
        }
        return false;
    }