leetcode-验证搜索二叉树

题目

https://leetcode-cn.com/problems/validate-binary-search-tree/

思路

• 中序遍历，结果是顺序的，用一个pre记录前面节点的值，因此当遍历的节点的值小于pre，就是二叉搜索树了。
• 递归，栈+迭代实现中序遍历
• 不要在leetcode使用全局变量！不要在leetcode使用全局变量！不要在leetcode使用全局变量！😭

AC代码

//迭代
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode *>s;
        long long pre = LLONG_MIN; //卡INT_MIN。。
        while (!s.empty() || root != NULL){
            while(root){ 	//将所有的left节点压入栈中
                s.push(root);
                root = root->left;
            }
            root = s.top(); //重点
            if(root->val <= pre){
                return false;
            }
            s.pop();
            pre = root->val;
            root = root->right;
        }
        return true;        
    }
};
           

//递归
class Solution {
public:
    void f(TreeNode * root, long long &pre,bool &res){
        if(root != NULL){
            f(root->left, pre,res);
            if(root->val <= pre)    res = false;
            pre = root->val;
            f(root->right,pre,res);
        }
    }
    bool isValidBST(TreeNode* root) {
        if(root == NULL)    return true;
        long long pre = LLONG_MIN;
        bool res = true;
        f(root,pre,res);
        return res;
    }
};