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:

▉ 问题分析

▉ 算法思路

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...

欢迎关注我个人公众号：「一个不甘平凡的码农」，记录了自己一路自学编程的故事。