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

我的方法一：递归

步骤

1. 为了看一个节点是否是二叉搜索树，那么需要保证左子树是BST、右子树是BST，左子树的最大值小于该节点；右子树的最小值比该节点大；
2. 递归判断每个节点，如果每个节点都符合，那么是BST；否则不是；

初始条件

边界条件

1. 当一个节点无子节点时，那么是BST；
2. 如果root为空，那么直接返回true

复杂度

时间复杂度：O(N)，最坏情况，需要遍历完所有节点才能获得最终结果
空间复杂度：O(N)，递归隐式使用了栈

代码

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(!root){
            return true;
        }

        int smallest;
        int biggest;
        return isValidBST(root, biggest, smallest);
    }

    bool isValidBST(TreeNode* node, int& biggest, int & smallest) {
        biggest = node->val;
        smallest = node->val;
        if(!node->left && !node->right){
            return true;
        }

        bool is_left_bst = true;
        bool is_right_bst = true;
        int left_biggest = node->val;
        int left_smallest = node->val;
        int right_biggest = node->val;
        int right_smallest = node->val;

        if(node->left){
            is_left_bst = isValidBST(node->left, left_biggest, left_smallest);
            if(!is_left_bst){
                return false;
            }

            if(left_biggest >= node->val){
                return false;
            }

            smallest = left_smallest;
        }

        if(node->right){
            is_right_bst = isValidBST(node->right, right_biggest, right_smallest);
            if(!is_right_bst){
                return false;
            }

            if(right_smallest <= node->val){
                return false;
            }

            biggest = right_biggest;
        }

        return true;
    }
};

我的方法二：二叉树中序遍历（迭代）

如果二叉树的节点满足二叉树特性，那么中序遍历正好是一个由小到大的排序，如果不不是从小到大，那么说明不满足二叉树特性

步骤

主要如何实现中序排列

1. 使用一个stack依次push节点以及他们的左节点
2. 当左节点保存完后，stack pop最近的这个左节点，该左节点就是在未遍历的节点中最小的那个节点
3. 遍历了该节点，再把右节点push到stack
4. 为了提前发现存在不满足特性的节点，可以记录下上一次遍历的节点值last_val

初始条件

1. 如果root为空，那么返回true
2. 先将root push到stack

边界条件

1. 当stack为空时，说明遍历完了所有节点，返回true
2. 如果有个节点的值比last_val相等或者小于，那么直接返回false

复杂度

时间复杂度：O(N)，最坏情况，需要遍历完所有节点才能获得最终结果
空间复杂度：O(N)，最坏情况，所有节点只有左子树

代码

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(!root){
            return true;
        }

        stack<TreeNode*> s;
        TreeNode* last_node = 0;
        while(!s.empty() || root){
            //push all left nodes to stack
            while(root){
                s.push(root);
                root = root->left;
            }

            // this is the smallest node, walk it
            root = s.top();
            s.pop();

            if(last_node){
                if(root->val <= last_node->val){
                    return false;
                }
            }
            last_node = root;
            root = root->right;
        }

        return true;
    }
};