題目描述

leetcode地址
二叉搜索樹是指：左子樹的節(jié)點(diǎn)值嚴(yán)格小于根節(jié)點(diǎn)，右子樹的節(jié)點(diǎn)值嚴(yán)格大于根節(jié)點(diǎn)。

源碼

現(xiàn)給出一個(gè)二叉樹，校驗(yàn)其是否滿足二叉搜索樹的特性。

比如下圖中，右節(jié)點(diǎn)4小于根節(jié)點(diǎn)5，不是二叉搜索樹。

截屏2021-03-01 上午11.27.15.png

思路分析

分解問題為一個(gè)一個(gè)的子問題，一顆大的二叉樹是搜索樹的前提是，其左右子樹也是二叉樹，只要在判斷子樹過(guò)程中發(fā)現(xiàn)有不滿足條件的，則整個(gè)二叉樹不滿足條件。

截屏2021-03-01 下午6.01.26.png

代碼實(shí)現(xiàn)

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    if(root === null || (root.left === null && root.right === null)) return true
    return recursive(root, -Infinity, Infinity)
    function recursive(node, left, right) {
        if(node === null) return true;
        if(node.val <= left || node.val >= right) return false
        return recursive(node.left, left, node.val) && recursive(node.right, node.val, right)
    }
};