Problem: 98. 验证二叉搜索树
解析
dfs递归法
传入三个参数，[当前节点，最小节点，最大节点]。如果当前节点为空，返回true。如果当前节点的值小于等于最小节点的值或者大于等于最大节点的值，返回false。否则递归判断左右子树。
这样可以避免使用[当前节点，左子树的最大值int，右子树的最小值int]来判断是否是二叉搜索树时需要的边界判定(当然也可以用long来避免这种边界判定)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
bool isValidBST(TreeNode *root) { return dfs(root, nullptr, nullptr); }
bool dfs(TreeNode *node, TreeNode *min_node, TreeNode *max_node) {
if (node == nullptr) {
return true;
}
if ((min_node && node->val <= min_node->val) ||
(max_node && node->val >= max_node->val)) {
return false;
}
return dfs(node->left, min_node, node) &&
dfs(node->right, node, max_node);
}
};
|
中序遍历
dfs递归法
中序遍历二叉搜索树，得到的序列是递增的。所以只需要判断中序遍历的序列是否是递增的即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
bool isValidBST(TreeNode *root) {
long current_min =LONG_MIN;
return inOrder(root,current_min); }
bool inOrder(TreeNode *node,long ¤t_min) {
if (node == nullptr) {
return true;
}
bool flag=true;
flag&=inOrder(node->left,current_min);
if(node->val<=current_min){
return false;
}
current_min =node->val;
flag&=inOrder(node->right,current_min);
return flag;
}
};
|
非递归法
使用栈模拟递归栈，中序遍历二叉搜索树，得到的序列是递增的。所以只需要判断中序遍历的序列是否是递增的即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
bool isValidBST(TreeNode *root) {
long current_min =LONG_MIN;
stack<TreeNode*> myStack;
TreeNode* node =root;
while (node!=nullptr || !myStack.empty()) {
while (node!=nullptr) {
myStack.push(node);
node=node->left;
}
node=myStack.top();
myStack.pop();
if(node->val<=current_min){
return false;
}
current_min =node->val;
node=node->right;
}
return true;
}
};
|
线索化
TODO
