乐趣区

LeetCode-之-JavaScript-解答第98题-验证二叉搜索树


Time:2019/4/24
Title: Vaildata Binary Search Tree
Difficulty: Medium
Author: 小鹿


题目:Vaildata Binary Search Tree(验证二叉搜索树)

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

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

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

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

Example 1:

Input:
    2
   / \
  1   3
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
             is 5 but its right child's value is 4.

Solve:

▉ 问题分析

看到此题的入手点就是上方提出的三点二叉搜索树的三点要求:

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

1)以上三点要求最容易解决的就是一个中序遍历,判断遍历出的每个元素后一个元素是否大于前一个元素,如果不符合条件,那么就不是一个二分搜索树。

▉ 算法思路

1)定义全局的 boolean 变量,用来返回是否为 二叉搜索树。

2)定义一个边界值赋予 max 变量。每遍历一次,如果符合前后大小的要求,就将当前节点的值赋值给 max 变量,用于下一次遍历的结点的大小比较。如果不符合要求,我们将其布尔变量置为 false。

3)整个过程是用递归来解决的,在理解上还是有点不符合常规思路的。也是整个问题分析中最重要的一点。

▉ 代码实现
var isValidBST = function(root) {
    // boolean 变量
    let isValidBSTFlag = true;
    // 最大值变量
    let max = -Number.MAX_VALUE;
    const orderSearch = root => {
        // 终止条件(判断当前结点是否为 null)if (root) {
            // 中序遍历
            orderSearch(root.left);
            // 判断遍历前后的值是否逐渐升序
            if (root.val > max) {
                // 存储当前结点值,进行下一次比较
                max = root.val;
            } else {
                // 当前节点值小于前一结点值,返回 false
                isValidBSTFlag = false;
            }
            orderSearch(root.right);
        }
    }
    orderSearch(root);
    return isValidBSTFlag;
};

欢迎一起加入到 LeetCode 开源 Github 仓库,可以向 me 提交您其他语言的代码。在仓库上坚持和小伙伴们一起打卡,共同完善我们的开源小仓库!
Github:https://github.com/luxiangqia…
欢迎关注我个人公众号:「一个不甘平凡的码农」,记录了自己一路自学编程的故事。

退出移动版