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

我的方法一：递归（错误的做法）

该方法验证是错误的，因为如果一个节点和它的左右子节点满足二叉树特性，但是可能该子节点的值和该节点的父节点不满足二叉树特性，如例子[10,5,15,null,null,6,20]，用该方法会返回true，但是实际是false。

步骤

1. 遍历每个节点，判断该节点的值是否比left大，并且比right小，如果不是那么返回false，如果是，则继续看看left和right子树是否满足

初始条件

边界条件

1. 如果某节点为空，那么该节点满足二叉树，返回true

复杂度

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

代码

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

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

        return isValidBST(root->left) && isValidBST(root->right);
    }
};

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

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

步骤

主要如何实现中序排列

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