验证二叉搜索树 Validate Binary Search Tree LeetCode

算法

搜索二叉树验证

二叉搜索树的判断需要借助中序遍历，中序遍历的序列需要是递增的才是二叉搜索树。因此有递归和递归方法的非递归形式，以及一种Morris遍历的方法。前两种方法都是O(n)的空间，Morris遍历是O(1)的方法。

递归解法

递归中用全局变量记录前驱指针

bool isValidBST(TreeNode* root) {
    isValid(root);
    return isValided;
}
bool isValided = true;
TreeNode* pre = NULL;
void isValid(TreeNode* cur)
{
    if(!cur || !isValided) return;
    isValid(cur->left);
    if(!pre){
        pre = cur;
    }else{
        if(pre -> val >= cur -> val)
        {
            isValided = false;
        }
        pre = cur;
    }
    isValid(cur->right);
}

栈解法

栈中节点作为当前节点，与前驱节点作比较

void isValidBST(TreeNode* root)
{
    vector<TreeNode*> vec;
    TreeNode *p = root, *pre = NULL;
    while(p || !vec.empty())
    {
        while(p)
        {
            vec.push_back(p);
            p = p -> left;
        }
        TreeNode* t = vec.back(); vec.pop_back();
        if(pre && t -> val <= pre->val) return false;
        pre = t;
        p = t -> right;
    }
    return true;
}

Morris中序遍历

Morris中序遍历是一种空间复杂度为O(1)的方法，只用到了cur和pre两个指针，cur指针指向当前节点，pre指向中序遍历顺序的前驱节点。

这个解法在

      5
     / \
    1   10
       /
      4

这种情况本地没问题，但是oj下会出现runtime error，不知道为什么。

bool isValidBST(TreeNode* root) {
    if(root == NULL) return true;
    TreeNode *cur = root, *pre = NULL, *parent = NULL;
    while(cur)
    {
        if(!cur -> left)
        {
            if(parent && parent->val >= cur->val) return false;
            parent = cur;
            cur = cur -> right;
        }else{
            pre = cur->left;
            while(pre->right && pre->right != cur )
                pre = pre->right;
            if(!pre->right)
            {
                pre->right = cur;
                cur = cur -> left;
            }else{
                pre -> right = NULL;
                if(pre->val >= cur->val) return false;
                parent = cur;
                cur = cur -> right;
            }
        }
    }
    return true;
}

参考：http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html