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   3Output: true

Example 2:

    5   / \  1   4     / \    3   6Output: falseExplanation: 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...
欢迎关注我个人公众号：「一个不甘平凡的码农」，记录了自己一路自学编程的故事。