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.
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
这道验证二叉搜索树有很多种解法，可以利用它本身的性质来做，即左<根<右，也可以通过利用中序遍历结果为有序数列来做，下面我们先来看最简单的一种，就是利用其本身性质来做，初始化时带入系统最大值和最小值，在递归过程中换成它们自己的节点值，用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); } };
Java 解法一：
public class Solution { public boolean isValidBST(TreeNode root) { if (root == null) return true; return valid(root, Long.MIN_VALUE, Long.MAX_VALUE); } public boolean valid(TreeNode root, long low, long high) { if (root == null) return true; if (root.val <= low || root.val >= high) return false; return valid(root.left, low, root.val) && valid(root.right, root.val, high); } }
这题实际上简化了难度，因为一般的二叉搜索树是左<=根<右，而这道题设定为左<根<右，那么就可以用中序遍历来做。因为如果不去掉左=根这个条件的话，那么下边两个数用中序遍历无法区分：
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); } };
Java 解法二：
public class Solution { public boolean isValidBST(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); inorder(root, list); for (int i = 0; i < list.size() - 1; ++i) { if (list.get(i) >= list.get(i + 1)) return false; } return true; } public void inorder(TreeNode node, List<Integer> list) { if (node == null) return; inorder(node.left, list); list.add(node.val); inorder(node.right, list); } }
下面这种解法跟上面那个很类似，都是用递归的中序遍历，但不同之处是不将遍历结果存入一个数组遍历完成再比较，而是每当遍历到一个新节点时和其上一个节点比较，如果不大于上一个节点那么则返回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; } };
Java 解法四：
public class Solution { public boolean isValidBST(TreeNode root) { Stack<TreeNode> s = new Stack<TreeNode>(); TreeNode p = root, pre = null; while (p != null || !s.empty()) { while (p != null) { s.push(p); p = p.left; } TreeNode t = s.pop(); if (pre != null && t.val <= pre.val) return false; pre = t; p = t.right; } return true; } }
最后还有一种方法，由于中序遍历还有非递归且无栈的实现方法，称之为Morris遍历，可以参考我之前的博客Binary Tree Inorder Traversal 二叉树的中序遍历，这种实现方法虽然写起来比递归版本要复杂的多，但是好处在于是O(1)空间复杂度，但是我的实现方法在本机上测试都能通过，在OJ上测试却有Runtime error，我找来找去不知道问题在哪，不管了先贴上来，说不定能引起某位大神的注意，帮小弟改一改哈~
C++ 解法五:
// Non-recursion without stack， I don't know why it cannot pass OJ, which show Runtime error. Can anyone help me fix it? Thanks! class Solution { public: bool isValidBST(TreeNode *root) { if (!root) return true; TreeNode *cur, *pre, *parent = NULL; cur = root; while (cur) { if (!cur->left) { if (parent && parent->val >= cur->val) return 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) return false; parent = cur; cur = cur->right; } } } return true; } };
本文转自博客园Grandyang的博客，原文链接：验证二叉搜索树[LeetCode] Validate Binary Search Tree ，如需转载请自行联系原博主。
