这个题一开始想当然了,对于节点node,如果
- node-val > node->left->val;
- node->val < node->right->val;
那么继续判断左右子树是否满足该性质,如果满足,那么该树就是一棵BST
但是这种方法只满足局部BST性质,举例来说:
2
/ \
1 5
/ \ / \
0 3 4 6
这个例子满足上面的性质:
- 对于节点2,其左子节点小于2,右子节点大于2
- 节点1的左子节点小于1,右子节点大于1
- 5的左子节点小于5,右子节点大于6
如果按照上面的逻辑,会判断这棵树是BST,但是在根节点2的左子树中,存在节点3,大于根节点2,所以实际上并不是一棵BST
中序遍历,如果是BST,那么中序遍历序列一定是递增的序列,只需要用一个变量维护已经遍历过的序列的最后一个值prev,通过比较当前节点的值和prev,如果依然满足递增的性质,那么继续判断,否则返回false