# C++ O(n) Time and O(1) Space recursion solution

• ``````class Solution {
/*The logic is that if the right child contains node whose value is smaller than that of current node, then the given order is invalid. */
public:
bool verifyPreorder(vector<int>& preorder) {
if(preorder.size() <= 1)
return true;
int n = preorder.size();
bool ispreorder = true;
dfs(0, 1, n, ispreorder, preorder);
return ispreorder;
}

private:
int dfs(int root_idx, int sta_idx, int end_idx, bool &ispreorder, vector<int>& preorder){
if(sta_idx >= end_idx)
return preorder[root_idx];
int idx = sta_idx, min_val;
for(; idx < end_idx; ++ idx){
if(preorder[idx] > preorder[idx - 1])
break;
}
//only has left child
if(idx >= end_idx){
return preorder[end_idx - 1];
}
//only has right child
if(idx == sta_idx){
min_val = dfs(root_idx + 1, sta_idx + 1, end_idx, ispreorder, preorder);
if(min_val < preorder[root_idx] || ispreorder == false){
ispreorder = false;
}
return min(min_val, preorder[root_idx]);
}

int nxt_idx = idx;
for(; nxt_idx < end_idx; ++ nxt_idx){
if(preorder[nxt_idx] > preorder[root_idx])
break;
}
//only has left child
if(nxt_idx >= end_idx){
//check the right child of current node's left child
min_val = dfs(idx, idx + 1, end_idx, ispreorder, preorder);
if(min_val < preorder[idx - 1] || ispreorder == false){
ispreorder = false;
}
return min(min_val, preorder[idx - 1]);
}
//check right child first
min_val = dfs(nxt_idx, nxt_idx + 1, end_idx, ispreorder, preorder);
if(min_val < preorder[root_idx] || ispreorder == false){
ispreorder = false;
return preorder[root_idx];
}
//then check the right child of current node's left child
min_val = dfs(idx, idx + 1, nxt_idx, ispreorder, preorder);
if(min_val < preorder[idx - 1] || ispreorder == false){
ispreorder = false;
}
return min(min_val, preorder[idx - 1]);
}
};``````

• This post is deleted!

• ``````#define SIZE(container) (int)(container).size()

// Tian Xia
class Solution {
public:
typedef int   Position;
typedef int   Value;

bool verifyPreorder(vector<int>& preorder) {
if (SIZE(preorder) <= 2) {
return true;
}

Value minv, maxv;
auto ret = traverse_son(preorder, 0, INT_MAX, minv, maxv);

return ret != -1;
}

protected:
Position traverse_son(const vector<int> &preorder,
Position pos, Value bound,
Value &minv, Value &maxv) {
Value root = preorder[pos];
Value left_min, left_max, right_min, right_max;
Position right_start = pos + 1;
minv = maxv = root;

if (pos + 1 >= SIZE(preorder)) {
return right_start;
}
else if (preorder[pos + 1] < root) {
right_start = traverse_son(preorder, pos + 1, root, left_min, left_max);
if (right_start == -1 || left_max > root) {
return -1;
}
minv = left_min;
}

if (right_start == SIZE(preorder) || preorder[right_start] > bound) {
return right_start;
}
else {
Position next_tree_start = traverse_son(preorder, right_start, bound,
right_min, right_max);
if (next_tree_start == -1 || right_min < root) {
return -1;
}
maxv = right_max;
return next_tree_start;
}
}
};
``````

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