Skip to content

Latest commit

 

History

History
30 lines (20 loc) · 1016 Bytes

File metadata and controls

30 lines (20 loc) · 1016 Bytes

误区

这个题一开始想当然了,对于节点node,如果

  1. node-val > node->left->val;
  2. 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