使用堆栈和顺序遍历检查Tree是否为BST

Question

这是我的代码，但它没有产生任何输出。

stack < int > st;
bool func(Node * root) {
if (root != NULL) {
func(root -> left);
st.push(root -> data);
func(root -> right);
}
while (!st.empty()) {
int upar = st.top();
st.pop();
if (upar > st.top()) {
continue;
} else {
return 0;
}
}
return 1;
}

请告诉我我缺了什么。我正确地追踪了代码，但它没有显示相关的结果。

Answer 1

我从代码中看到的是，函数func()被递归调用，但它的返回值从未被检查过。如果它意味着将东西推入堆栈以创建按顺序遍历，那应该没问题，但您还包含了while循环来检查数据是否按升序排列。这就是问题所在。

我能想到的最简单的解决方案是将其一分为二：

stack < int > st;
void func(Node * root) {
if (root != NULL) {
func(root -> left);
st.push(root -> data);
func(root -> right);
}
}
bool check(Node* root) {
func(root);
while (!st.empty()) {
int upar = st.top();
st.pop();
if (upar > st.top()) {
continue;
} else {
return 0;
}
}
return 1;
}

但您必须检查是否假设BST中没有重复条目，因为您使用的是upar > st.top()而不是>=。

如果您坚持将两者合并为一个函数，您可以考虑更改func()，以在Node*之外传递值的上限或下限，这样您就可以相应地检查左右子树。在这种情况下，您可以跳过堆叠的使用。但从根节点开始，从负无穷大到正无穷大。执行递归时，将root->data替换为左树上的上界和右树上的下界。