C++ simple recursive with range checking

  • 0

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

    class Solution {
        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
            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.