题解 | #判断是不是二叉搜索树#

/*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)
 *     }
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return bool布尔型
 */

/**
 * 方法一：递归
 * 时间复杂度：O(n)，访问二叉树所有节点各一次
 * 空间复杂度：O(n)
 */
// export function isValidBST(root: TreeNode): boolean {
//     if (root === null) return true
//     const resArr: number[] = []
    
//     // 递归方法：获取中序遍历数组
//     inOrder(root, resArr)
    
//     // 判断中序遍历数组是否递增，不是则直接 return false
//     for (let i = 0; i < resArr.length - 1; i++) {
//         if (resArr[i] >= resArr[i + 1]) return false
//     }
    
//     return true
// }

// function inOrder(root: TreeNode, resArr: number[]) {
//     if (root === null) return 
//     inOrder(root.left, resArr) 
//     resArr.push(root.val)
//     inOrder(root.right, resArr) 
// }

/**
 * 方法二：非递归
 * 时间复杂度：O(n)，访问二叉树所有节点各一次
 * 空间复杂度：O(n)
 */
export function isValidBST(root: TreeNode): boolean {
    if (root === null) return true
    const resArr: number[] = []
    
    // 非递归方法：获取中序遍历数组
    inOrder(root, resArr)
    
    // 判断中序遍历数组是否递增，不是则直接 return false
    for (let i = 0; i < resArr.length - 1; i++) {
        if (resArr[i] >= resArr[i + 1]) return false
    }
    
    return true
}

function inOrder(root: TreeNode, resArr: number[]) {
    let node: TreeNode = root
    const stack: TreeNode[] = []
    while (stack.length || node) {
        while (node) {
            stack.push(node)
            node = node.left
        }
        const top = stack.pop()
        resArr.push(top.val)
        node = top.right
    }
}