这题在leetcode上是用中序遍历来做的，但是这里由于有相等的情况，即左子树小于等于根，这样中序遍历无法完全判定。可以用递归来做，用递归给出每个子树的上下界。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <climits>bool
isBSTRecur(TreeNode *root, int
leftVal, int
rightVal) {
if
(root == NULL) return
true;
return
(root->val <= rightVal) &&
(root->val > leftVal) &&
isBSTRecur(root->left, leftVal, root->val) &&
isBSTRecur(root->right, root->val, rightVal);
}/*树结点的定义(请不要在代码中定义该结构)struct TreeNode { int val;
TreeNode *left, *right;
}*/bool
isBST(TreeNode *root) {
return
isBSTRecur(root, INT_MIN, INT_MAX);
} |