;(function(){
    /**
     * 98. 验证二叉搜索树
     * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
     * 有效 二叉搜索树定义如下：
     *  -- 1. 节点的左子树只包含 小于 当前节点的数。
     *  -- 2. 节点的右子树只包含 大于 当前节点的数。
     *  -- 3. 所有左子树和右子树自身必须也是二叉搜索树。
     * 
     * 输入：root = [2,1,3]
     * 输出：true
     * 
     * 输入：root = [5,1,4,null,null,3,6]
     * 输出：false
     * 解释：根节点的值是 5 ，但是右子节点的值是 4 。
     * 
     * [2,2,2] -- false
     * [1,null,1] -- false
     * [5,4,6,null,null,3,7] -- false
     * [0,null,-1] -- false
     * [32,26,47,19,null,null,56,null,27] -- false
     */

    class TreeNode {
        val: number
        left: TreeNode | null
        right: TreeNode | null
        constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
            this.val = (val===undefined ? 0 : val)
            this.left = (left===undefined ? null : left)
            this.right = (right===undefined ? null : right)
        }
    }

    function isValidBST(root: TreeNode | null): boolean {
        // 方法一：递归（官方提供）
        // const helper = (root: TreeNode | null, lower: number, upper: number): boolean => {
        //     if (root === null) {
        //         return true;
        //     }
        //     if (root.val <= lower || root.val >= upper) {
        //         return false;
        //     }
        //     return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);
        // }
        // return helper(root, -Infinity, Infinity);

        // 方法二：中序遍历（官方提供）
        let stack = [];
        let inorder = -Infinity;
        while (stack.length || root !== null) {
            while (root !== null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop() || null;
            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root) {
                if (root.val <= inorder) {
                    return false;
                }
                inorder = root.val;
                root = root.right;
            }
        }
        return true;

        // 方法三：
    };

})()