Validate Binary Search Tree

Oct 23, 2017

第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:

    2
   / \
  1   3

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

    1
   / \
  2   3

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

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

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

 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);
    }

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

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中有一些其他方法:

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);
}
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);
}
LeetCodeLeetCode

Binary Tree Level Order Traversal

Unique Binary Search Tree

comments powered by Disqus