Code & Fun

第30天。

恍恍惚惚就一个月了。

今天的题目是Validate Binary Search Tree:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Example 1:

1
2
3
  2
/ \
1 3

Binary tree [2,1,3], return true.
Example 2:

1
2
3
  1
/ \
2 3

Binary tree [1,2,3], return false.

昨天的题目也是和BST有关的,但是这里的定义和昨天有点不用,它这里要求左子树的所有节点都比根节点的值要小,右子树的所有的节点的值都比根节点的值大.

我们可以发现这样定义的BST的中序遍历一定是升序的,所以我们可以用先序遍历的方式来做:

1
2
3
4
5
6
7
8
long long vmax = LLONG_MIN;
bool isValidBST1(TreeNode* root) {
if (root == NULL) return true;
if ( !isValidBST(root->left) ) return false;
if (root->val <= vmax) return false;
vmax = root->val;
return isValidBST(root->right);
}

既然使用中序遍历做的,那么我们就可以用非递归版的先序遍历来加快:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
long long vmax = LLONG_MIN;
bool isValidBST(TreeNode* root) {
stack<TreeNode *> st;
while(true) {
while(root){
st.push(root);
root = root->left;
}

if (st.empty()) break;
root = st.top();
st.pop();

if (vmax >= root->val) return false;
vmax = root->val;

root = root->right;
}
return true;
}

上面都是用long long来记录最大值,这时因为如果用INT_MIN来做的话,[INT_MIN,INT_MIN]这样的测例就会出错,我是用long long来解决这个问题的,但是dicuss中有一些其他方法:

1
2
3
4
5
6
7
8
9
10
11
bool isValidBST(TreeNode* root) {
TreeNode* prev = NULL;
return validate(root, prev);
}
bool validate(TreeNode* node, TreeNode* &prev) {
if (node == NULL) return true;
if (!validate(node->left, prev)) return false;
if (prev != NULL && prev->val >= node->val) return false;
prev = node;
return validate(node->right, prev);
}
1
2
3
4
5
6
7
8
9
10
bool isValidBST(TreeNode* root) {
return isValidBST(root, NULL, NULL);
}

bool isValidBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
if(!root) return true;
if(minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val)
return false;
return isValidBST(root->left, minNode, root) && isValidBST(root->right, root, maxNode);
}

本文首发于Code & Fun