LeetCode 98 [Validate Binary Search Tree]

题目链接

题目描述

  • 判断给定的二叉树是不是二叉排序树,假定二叉排序树满足以下条件:
    1. 任意一个结点的左子树的所有结点的值都比该结点小
    2. 任意一个结点的右子树的所有结点的值都比该结点大
    3. 左子树和右子树都是二叉排序树(递归定义)

解题思路

  • 根据二叉排序树的定义,从根结点出发,验证以每一个结点为根的树是否满足条件
  • 对每一个被遍历的结点,若左子结点不为空,则查找左子树的所有结点的最大值,若该值不小于当前结点的值,则说明当前树不是二叉排序树,否则继续查找右子树的所有结点的最小值,若该值不大于当前结点的值,则同样说明当前树不是二叉排序树
  • 实际代码实现使用递归的方式,最大值被初始化为整型的最小值,最小值被初始化为整型的最大值,由上层调用时传入

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (!root) {
return true;
}
int max = INT_MIN;
int min = INT_MAX;
return travel(root, max, min);
}
bool travel(TreeNode* node, int& max, int& min) {
max = node->val > max ? node->val : max;
min = node->val < min ? node->val : min;
int tmpmax, tmpmin;
if (node->left) {
tmpmax = INT_MIN;
tmpmin = INT_MAX;
if (!travel(node->left, tmpmax, tmpmin)) {
return false;
} else if (tmpmax >= node->val) {
return false;
}
max = tmpmax > max ? tmpmax : max;
min = tmpmin < min ? tmpmin : min;
}
if (node->right) {
tmpmax = INT_MIN;
tmpmin = INT_MAX;
if (!travel(node->right, tmpmax, tmpmin)) {
return false;
} else if (tmpmin <= node->val) {
return false;
}
max = tmpmax > max ? tmpmax : max;
min = tmpmin < min ? tmpmin : min;
}
return true;
}
};