[LeetCode C++实现]98. Validate Binary Search Tree

98. Validate Binary Search Tree
验证给定二叉树是否是二叉搜索树，个人认为属于面试题中的高频题目。
首先我们用最直观最暴力最ugly的代码先AC(中序遍历，验证vector中是否有重复元素是否是升序)：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        vector<int> inorder;
        inorder_bst(root,inorder);
        vector<int> sorted(inorder);
        sort(sorted.begin(),sorted.end());
        vector<int>::iterator it = unique(sorted.begin(),sorted.end());
        //去除重复元素
        sorted.erase(it,sorted.end());
        if(sorted.size() != inorder.size())
            return false;
        
        if (equal(inorder.begin(), inorder.begin() + inorder.size(), sorted.begin()))
            return true;
            
        return false;
    }
    
private:
void inorder_bst(TreeNode * root,vector<int> & inorder)
{
    if(root == NULL)
        return;
    inorder_bst(root->left,inorder);
    inorder.push_back(root->val);
    inorder_bst(root->right,inorder);
}
};

运行效率有点意外，就这居然击败了近一半人的提交：

Runtime: 20 ms, faster than 45.02% of C++ online submissions for Validate Binary Search Tree.
Memory Usage: 22.3 MB, less than 93.69% of C++ online submissions for Validate Binary Search Tree.

一种巧妙解法，通过维护一个prev，保存中序遍历后的前一个元素，如果前一个元素大于等于当前节点那么则不是二叉搜索树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode * prev = NULL;
        return validate(root,prev);
    }
private:
    bool validate(TreeNode* node, TreeNode* &prev) {
        if(!node) return true;
        if(!validate(node->left,prev)) return false;
        if(prev && prev->val >= node->val) return false;
        prev = node;
        return validate(node->right,prev);
    }
};

通过这道题对递归有了进一步的理解，对比本文自己手写的方法一，简直不知道高几个level。年轻人还是too young too naive。
C++ in-order traversal, and please do not rely on buggy INT_MAX, INT_MIN solutions any more
2021.03.07更新记录：
递归方法，每次传入左边界或右边界，对左子树操作时，由于所有值要小于当前值，因此更新右边界，对右子树更新时，由于所有值要大于root->val，因此更新左边界。这里有一个小技巧，由于树中值的范围是int,因此参数使用long long，这样可以确保树中INT_MIN INT_MAX，可以小于或大于 LONG_MIN和LONG_MAX，这种解法存在限制：
1、如果当前数据类型已是最小范围，判断会存在问题,例如树只有一个结点，值是TYPE_MIN或TYPE_MAX
2、上面例子或许存在跨平台问题，在32位系统中运行可能存在异常，long long只有在64位系统中才战8个字节，在32位系统中还是占用4个字节，因此和int范围相同，存在第1点所说的问题。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(root == nullptr) return true;
        return isValidBST(root,LONG_MIN,LONG_MAX);
    }
private:
    bool isValidBST(TreeNode* root,long long left_bound,long long right_bound){
        if(root == nullptr) return true;
        if(root->val <= left_bound || root->val >= right_bound )
            return false;
        return isValidBST(root->left,left_bound,root->val) && isValidBST(root->right,root->val,right_bound);
    }
};

学习讨论区中的解法，一个非常巧妙的算法如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBST(root,NULL,NULL);
    }
private:
    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);
    }
};

这里巧妙的利用了两个参数保存最小结点和最大结点，利用二叉搜索树的特性，左子树所有元素都小于根节点，右子树所有元素都大于根节点，左子树不指定下限，右子树不指定上限。
运行效率：

Runtime: 12 ms, faster than 93.30% of C++ online submissions for Validate Binary Search Tree.
Memory Usage: 22 MB, less than 93.69% of C++ online submissions for Validate Binary Search Tree.

2021.03.07更新代码:

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(root == nullptr) return true;
        return isValidBST(root,nullptr,nullptr);
    }
private:
    bool isValidBST(TreeNode* root,TreeNode* left_bound,TreeNode* right_bound){
        if(root == nullptr) return true;
        if(left_bound && root->val <= left_bound->val ||
           right_bound && root->val >= right_bound->val)
            return false;
        return isValidBST(root->left,left_bound,root) && isValidBST(root->right,root,right_bound);
    }
};

运行效率:

Runtime: 16 ms, faster than 48.77% of C++ online submissions for Validate Binary Search Tree.
Memory Usage: 21.5 MB, less than 85.86% of C++ online submissions for Validate Binary Search Tree.

个人认为最具技术含量的方法还是上面中序遍历的方法，中序遍历每个人都会，但通过一个prev指针，中序遍历不断更新prev，然后跟当前结点比较，如果不符合中序遍历特点，那么就不是二叉搜索树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = nullptr;
        return visited(root,prev);
    }
private:
    bool visited(TreeNode* root,TreeNode* &prev) {
        if(root == nullptr) return true;
        if(!visited(root->left,prev))
            return false;
        if(prev && prev->val >= root->val) 
            return false;
        prev = root;
        return visited(root->right,prev);
    }
};

运行结果:

Runtime: 20 ms, faster than 22.92% of C++ online submissions for Validate Binary Search Tree.
Memory Usage: 21.5 MB, less than 85.86% of C++ online submissions for Validate Binary Search Tree.

2021.09.13更新

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = nullptr;
        return visit(root);
    }
private:
    TreeNode* prev = nullptr;
    bool visit(TreeNode* root)
    {
        if(!root) return true;
        if(!visit(root->left)) return false;
        if(prev && prev->val >= root->val) return false;
        prev = root;
        return visit(root->right);
    }
};

这里如果不使用全局变量，写法：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = nullptr;
        return visited(root,prev);
    }
private:
    bool visited(TreeNode* root,TreeNode* &prev) {
        if(root == nullptr) return true;
        if(!visited(root->left,prev))
            return false;
        if(prev && prev->val >= root->val) 
            return false;
        prev = root;
        return visited(root->right,prev);
    }
};

为什么函数参数要写成TreeNode* &prev呢？
原因是需要根据中序遍历，记录上一个元素的值，当前root->val跟prev->val去比较，因此可以使用指针的引用来解决，习惯写C语言的朋友，可以使用指针的指针来解决这个问题。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = nullptr;
        return visit(root,&prev);
    }
private:
    bool visit(TreeNode* root,TreeNode** prev)
    {
        if(!root) return true;
        if(!visit(root->left,prev)) return false;
        if(prev && *prev &&(*prev)->val >= root->val) return false;
        *prev = root;
        return visit(root->right,prev);
    }
};

52coder

[LeetCode C++实现]98. Validate Binary Search Tree