验证二叉搜索树

JavaScript实现leetcode98. 验证二叉搜索树

题目描述

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

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

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

示例 1:

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

示例 2:

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

思路分析

最开始看到这道题的时候，以为是直接判断 node.right.val > node.val 和 node.left.val < node.val 对每个结点是否成立。但是这种是忽略了，二叉搜索树还有一个很重要的特点就是，左子树上所有节点的值均小于它的根节点的值，右子树上所有节点的值均大于它的根节点的值。注意是左子树和右子树所有的节点都满足才行。

所以需要加一个界限的判断。

解题步骤

1. 一个递归函数 isValidBSTCore(root, lower, upper) 来递归判断函数表示考虑以 root 为根的子树，判断子树中所有节点的值是否都在 (l,r)(l,r) 的范围内（注意是开区间）。
   • 如果 root 节点的值 val 不在 (l,r)(l,r) 的范围内说明不满足条件直接返回
   • 否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。
2. 根据二叉搜索树的性质，进行递归逻辑的判断
   • 在递归调用左子树时，我们需要把上界 upper 改为 root.val，即调用 isValidBSTCore(root.left, lower, root.val)，因为左子树里所有节点的值均小于它的根节点的值。
   • 同理递归调用右子树时，我们需要把下界 lower 改为 root.val，即调用 isValidBSTCore(root.right, root.val, upper)。

解题方法

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
   // 判断是否在界限内部
    function isValidBSTCore(root, lower, upper) {
        // 如果是null，则返回 true
        if(root === null) {
            return true;
        }
        if(lower !== null && root.val <= lower) {
            return false
        }
        if(upper !== null && root.val >= upper) {
            return false
        }
        // 对子树进行递归
        return isValidBSTCore(root.left, lower, root.val)  &&  isValidBSTCore(root.right, root.val, upper);
    }
    return isValidBSTCore(root, null, null)
};

复杂度分析

• 时间复杂度：O(n)，其中 n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)。
• 空间复杂度：O(n)，其中 n 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况下二叉树为一条链，树的高度为 n ，递归最深达到 nn 层，故最坏情况下空间复杂度为 O(n) 。

参考

• leetcode官方题解[1]

参考资料

[1]

leetcode官方题解: https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode-solution/