下面代码好像可以跑过几个case, 就是用两个 minStack, maxStack,在 traverse
list
同时判断是否是valid BST.
bool listValidBSTHelper(stack &minsk, stack &maxsk, list::
iterator &it, list &l) {
if (it == l.end()) return true;
if (minsk.empty() || maxsk.empty()) return false;
if (*it <= minsk.top() || *it >= maxsk.top()) {
int val = maxsk.top();
maxsk.pop();
minsk.push(val);
return listValidBSTHelper(minsk, maxsk, it, l);
}
maxsk.push(*it);
it++;
if (false == listValidBSTHelper(minsk, maxsk, it, l)) return false;
if (false == listValidBSTHelper(minsk, maxsk, it, l)) return false;
return true;
}
bool isListValidBST(list &l) {
list::iterator it = l.begin();
stack minsk, maxsk;
minsk.push(INT_MIN);
maxsk.push(INT_MAX);
return listValidBSTHelper(minsk, maxsk, it, l);
}