@markheng 2018-04-10T13:52:55.000000Z 字数 1306 阅读 1173

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

算法

## 递归解法

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


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

• 私有
• 公开
• 删除