Code & Func

第30天。

恍恍惚惚就一个月了。

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:

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

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

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

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

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

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

1
long long vmax = LLONG_MIN;
2
bool isValidBST(TreeNode* root) {
3
    stack<TreeNode *> st;
4
    while(true) {
5
        while(root){
6
            st.push(root);
7
            root = root->left;
8
        }
9

10
        if (st.empty()) break;
11
        root = st.top();
12
        st.pop();
13

14
        if (vmax >= root->val) return false;
15
        vmax = root->val;
5 collapsed lines
16

17
        root = root->right;
18
    }
19
    return true;
20
}

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

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

1
bool isValidBST(TreeNode* root) {
2
    return isValidBST(root, NULL, NULL);
3
}
4

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