本周主题：DFS
本题难度：Medium
做题日期：2017年4月17日
98. Validate 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:
2
/ \
1 3
Binary tree
[2,1,3]
, return true.
Example 2:
1
/ \
2 3
Binary tree
[1,2,3]
, return false.
https://leetcode.com/problems/validate-binary-search-tree/#/description
什么是 BST?
如下是百度百科的定义：
二叉查找树（Binary Search Tree），（又：
二叉搜索树
，二叉排序树）它或者是一棵空树，或者是具有下列性质的
二叉树
： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为
二叉排序树
。
二叉搜索树是一种非常重要的数据结构，应用比较广泛。它可以通过 中序遍历，将无序的序列转变成一个递增的有序序列。它也是很多高效搜索的数据结构的基础，比如 B树，B+树 和 B* 树。
本题是要我们判断一颗树是不是二叉搜索树。其判断方法有很多种，下面我们逐一讲解。
方案一
根据BST的定义，我们只需要判断当前树是否满足如下三个条件
-
-
左子树的所有节点都小于当前节点的值；右子树的所有节点都大于当前节点
-
代码如下
优点
-
比较符合正常的逻辑思考
-
思路比较清晰
缺点
-
-
方案二
由于树是递归定义的，所以我们只需要判断当前的节点是否在一个取值区间即可。
优点： 代码简单，逻辑清晰
缺点：不容易想到，对coder的能力要求比较高，需要对树的递归遍历比较熟悉
优化版本
使用 Long.MIN_VALUE 代码 Integer.MIN_VALUE ，不需要考虑 节点的边界值，代码更少更健壮。
方案三
利用中序遍历的特性，将树转换成一个数组，然后判断该数组是不是递增的
灵活运用中序遍历的特点：BST通过中序遍历会构建一个递增的有序序列。通过判断数组 res 是不是有序的来判断树是不是 BST。
如果对中序遍历比较了解，这种解法的思路特别简单。如果对中序遍历的特点不了解，不容易想到。
上面的代码是中序遍历的递归代码，如下的代码是中序遍历的非递归实现。
