Clean c++ dfs solution


  • 2

    Go left as far as possible, then go right

    bool verifyPreorder(vector<int>& preorder) {
        int index = 0;
        verifyPreorder(preorder, index, INT_MIN, INT_MAX);
        return index == preorder.size();
    }
    
    void verifyPreorder(vector<int>& preorder, int &index, int low, int high) {
        if (index == preorder.size() || preorder[index] < low || preorder[index] > high)
            return;
        int current = preorder[index++];
        verifyPreorder(preorder, index, low, current - 1);
        verifyPreorder(preorder, index, current + 1, high);
    }
    

Log in to reply
 

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