C++ simple recursive with range checking


  • 0
    H

    This solution figure the range for each node and its children, do the checking recursively. check left first, then right tree.

    class Solution {
    public:
        bool verifyPreorder(vector<int>& preorder) {
            if (preorder.size()<=1) return true;
            int tmin=INT_MIN, tmax=INT_MAX;
            
            int idx=0;
            return verify2(preorder, idx, INT_MIN, INT_MAX);
        }
        
        bool verify2(vector<int>& preorder, int& idx, int tmin, int tmax) {
            if (idx>=preorder.size()) return true; // reaching the end of the array, rewind the stack
            // check current root
            if (preorder[idx]<=tmin || preorder[idx]>=tmax) return false;
            
            int curr_root=preorder[idx];
            // check left
            ++idx;
            if (verify2(preorder, idx, tmin, curr_root)) return true;
            
            // check right
            return verify2(preorder, idx, curr_root, tmax);        
        }
    };
    

Log in to reply
 

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