Heading

98.验证二叉搜索树 (opens new window)

Tags: algorithms amazon bloomberg facebook microsoft tree depth-first-search

Langs: c cpp csharp golang java javascript kotlin php python python3 racket ruby rust scala swift typescript

• algorithms
• Medium (33.31%)
• Likes: 921
• Dislikes: -
• Total Accepted: 221.4K
• Total Submissions: 660.7K
• Testcase Example: '[2,1,3]'

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

/*
 * @lc app=leetcode.cn id=98 lang=javascript
 *
 * [98] 验证二叉搜索树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
    const isValidBSTEx = function (root, lower = -Infinity, upper = Infinity) {
        if (root === null) return true;
        if (root.val <= lower || root.val >= upper) return false;
        //递归时，遍历左子树时更新上界（所有节点都小于根节点），遍历右子树时更新下界（所有节点都大于根节点）
        return isValidBSTEx(root.left, lower, root.val) && isValidBSTEx(root.right, root.val, upper);
    }

    return isValidBSTEx(root);
};
/**
 * @param {TreeNode} root
 * @return {boolean}
 * 二叉搜索树的中序遍历一定是一个递增序列
 */
var isValidBST = function (root) {
    if(root === null) return true;
    let p = root,q;
    let min = -Infinity;
    const stack = [];
    while(p || stack.length){
        while(p){
            stack.push(p);
            p = p.left;
        }
        q = stack.pop();
        if(q.val <= min){
            return false;
        }else{
            min = q.val;
        }
        p = q.right;
    }
    return true;
};
// @lc code=end


// @after-stub-for-debug-begin
module.exports = isValidBST;
// @after-stub-for-debug-end