验证二叉搜索树¶
leetcode 98 题，难度中等，考察二叉搜索树的特征和遍历
题目描述：
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
解题思路：
这道验证二叉搜索树有很多种解法，可以利用它本身的性质来做，即左<根<右，也可以通过利用中序遍历结果为有序数列来做，下面我们先来看最简单的一种，就是利用其本身性质来做，初始化时带入系统最大值和最小值，在递归过程中换成它们自己的节点值，用long代替int就是为了包括int的边界条件，代码如下：
C++ 解法一：
// Recursion without inorder traversal
class Solution {
public:
bool isValidBST(TreeNode *root) {
return isValidBST(root, LONG_MIN, LONG_MAX);
}
bool isValidBST(TreeNode *root, long mn, long mx) {
if (!root) return true;
if (root->val <= mn || root->val >= mx) return false;
return isValidBST(root->left, mn, root->val) && isValidBST(root->right, root->val, mx);
}
};
JS 基本代码（递归树节点）
function isValidBST(root) {
function check(node, min, max) {
if (!node) {
return true;
}
if (node.val > max || node.val < min) {
return false;
}
return check(node.left, min, node.val) && check(node.right, node.val, max);
}
// 先假设树顶点的最大值和最小值，顶点 val 无限制
let MIN = -Infinity;
let MAX = Infinity;
return check(root, MIN, MAX);
}
这题实际上简化了难度，因为一般的二叉搜索树是左<=根<右，而这道题设定为左<根<右，那么就可以用中序遍历来做。因为如果不去掉左=根这个条件的话，那么下边两个数用中序遍历无法区分：
20 20 / \ 20 20
它们的中序遍历结果都一样，但是左边的是BST，右边的不是BST。去掉等号的条件则相当于去掉了这种限制条件。下面我们来看使用中序遍历来做，这种方法思路很直接，通过中序遍历将所有的节点值存到一个数组里，然后再来判断这个数组是不是有序的，代码如下：
C++ 解法二：
// Recursion
class Solution {
public:
bool isValidBST(TreeNode *root) {
if (!root) return true;
vector<int> vals;
inorder(root, vals);
for (int i = 0; i < vals.size() - 1; ++i) {
if (vals[i] >= vals[i + 1]) return false;
}
return true;
}
void inorder(TreeNode *root, vector<int> &vals) {
if (!root) return;
inorder(root->left, vals);
vals.push_back(root->val);
inorder(root->right, vals);
}
};
JS 基本代码（二叉搜索树中序遍历，结果是有序数组）先忽略 val 是 0 的特殊情况
function isValidBST(root) {
let list = [];
function runNode(node) {
// 左
if (node && node.left) {
runNode(node.left);
}
// 中
if (node && node.val) {
// 判断中序遍历的结果，是否是有序数组
if (node.val < list[list.length - 1]) {
list.push(node.val);
} else {
return false;
}
}
// 右
if (node && node.right) {
runNode(node.right);
}
}
}
下面这种解法跟上面那个很类似，都是用递归的中序遍历，但不同之处是不将遍历结果存入一个数组遍历完成再比较，而是每当遍历到一个新节点时和其上一个节点比较，如果不大于上一个节点那么则返回false，全部遍历完成后返回true。代码如下：
C++ 解法三：
// Still recursion
class Solution {
public:
TreeNode *pre;
bool isValidBST(TreeNode *root) {
int res = 1;
pre = NULL;
inorder(root, res);
if (res == 1) return true;
else false;
}
void inorder(TreeNode *root, int &res) {
if (!root) return;
inorder(root->left, res);
if (!pre) pre = root;
else {
if (root->val <= pre->val) res = 0;
pre = root;
}
inorder(root->right, res);
}
};
当然这道题也可以用非递归来做，需要用到栈，因为中序遍历可以非递归来实现，所以只要在其上面稍加改动便可，代码如下：
C++ 解法四：
// Non-recursion with stack
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> s;
TreeNode *p = root, *pre = NULL;
while (p || !s.empty()) {
while (p) {
s.push(p);
p = p->left;
}
TreeNode *t = s.top(); s.pop();
if (pre && t->val <= pre->val) return false;
pre = t;
p = t->right;
}
return true;
}
};
最后还有一种方法，由于中序遍历还有非递归且无栈的实现方法，称之为Morris遍历，可以参考http://www.cnblogs.com/grandyang/p/4297300.html,这种实现方法虽然写起来比递归版本要复杂的多，但是好处在于是O(1)空间复杂度，参见代码如下：
C++ 解法五:
class Solution {
public:
bool isValidBST(TreeNode *root) {
if (!root) return true;
TreeNode *cur = root, *pre, *parent = NULL;
bool res = true;
while (cur) {
if (!cur->left) {
if (parent && parent->val >= cur->val) res = false;
parent = cur;
cur = cur->right;
} else {
pre = cur->left;
while (pre->right && pre->right != cur) pre = pre->right;
if (!pre->right) {
pre->right = cur;
cur = cur->left;
} else {
pre->right = NULL;
if (parent->val >= cur->val) res = false;
parent = cur;
cur = cur->right;
}
}
}
return res;
}
};