Validate Binary Search Tree
update Jul 14, 2017 18:13
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. A single node tree is a BST
Example:
An example:
2
/ \
1 4
/ \
3 5
The above binary tree is serialized as {2,1,4,#,#,3,5} (in level order).
Basic Idea:
利用定义，每一个子树都需要是vlaid bst。对于每个root，需要保证root.val 大于左子树中的最大值，小于右子树的最小值。由此，我们可以定义一个ReturnType，其中包含boolean isValid, max, min三个变量。
（需要注意的是，当node的值是Integer.MAX_VALUE的时候，会造成边界判定不准，可以转成(long)Integer.MAX_VALUE + 1之类来处理）
Java Code:
public class Solution {
/**
* @param root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/
// 使用分治法
private class Return {
boolean isValid = true;
long min = Integer.MAX_VALUE;
long max = Integer.MIN_VALUE;
public Return(boolean b, long min, long max) {
isValid = b;
this.min = min;
this.max = max;
}
}
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
Return ret = helper(root);
return ret.isValid;
}
private Return helper(TreeNode root) {
if (root == null) return new Return(true, (long)Integer.MAX_VALUE + 1, (long)Integer.MIN_VALUE - 1);
if (root.left == null && root.right == null) {
return new Return(true, root.val, root.val);
}
Return left = helper(root.left);
Return right = helper(root.right);
boolean flag = true;
long max = Math.max(left.max, Math.max(right.max, root.val));
long min = Math.min(left.min, Math.min(right.min, root.val));
if (! left.isValid || ! right.isValid || root.val >= right.min || root.val <= left.max) {
flag = false;
}
return new Return(flag, min, max);
}
}
update Aug 27, 2017 20:39
更新一个Python的解法，和前面Java的思路类似，但是这次我们不使用boolean flag，而是当我们检测到当前树invalid时，直接返回None； 另外还有一种思路，最简单的，就是inorder遍历一遍，然后验证生成的数组是否是递增的，但是这种方法有局限，就是无法判断如下情况：
1 1
/ \ --------- \
1 1 1
\
1
有相同的 inorderList: [1,1,1]
但因为此题规定二叉树左右和root一定不相等，所以不用考虑这种情况，所以inorder traverse 是可以用的。
Python:
class Solution(object):
def isValidBST(self, root):
# 返回（min, max），如果检查出已经invalid，返回None
def helper(root):
if not root:
return (float('inf'), float('-inf'))
left = helper(root.left)
right = helper(root.right)
if not left or not right:
return None
if left[1] >= root.val or right[0] <= root.val:
return None
return (min(left[0], right[0], root.val), max(left[1], right[1], root.val))
return helper(root) is not None
update Dec 20, 2017 15:30
Update
更新一种解法，返回值只用于判断左右子树是否为valid，而找 leftMax 和 rightMin 依靠每层递归中的 while 循环；
Java Code
public class Solution {
/*
* @param root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (! isValidBST(root.left) || ! isValidBST(root.right)) {
return false;
}
long leftMax;
long rightMin;
TreeNode node = root.left;
while (node != null && node.right != null) node = node.right;
leftMax = node != null ? node.val : (long)Integer.MIN_VALUE - 1;
node = root.right;
while (node != null && node.left != null) node = node.left;
rightMin = node != null ? node.val : (long)Integer.MAX_VALUE + 1;
if (root.val > leftMax && root.val < rightMin) return true;
else return false;
}
}
再更新一种 iterative 的解法，就是简单的 inorder traversal，检查是否严格单调递增，对于这种没有重复元素的BST很好用。
# inorder traversal, check if is increasing
class Solution:
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root: return True
stack = []
while root:
stack.append(root)
root = root.left
prev = float('-inf') # 跟踪前一个元素，初始化为负无穷
while stack:
node = stack.pop()
if node.val <= prev: # 说明不是递增，则不是BST
return False
prev = node.val # 更新prev
node = node.right
while node:
stack.append(node)
node = node.left
return True
update Jan,4 2017 15:36
Update
更新一种解法，每次递归时传入两个边界
这种解法有些像 alpha-beta pruning：
- 递归传入两个另外参数，alpha 为 lower bound，beta 为 upper bound，初始化分别为
-inf和inf； - 每次进入当前node，判断当前 node.val 是否在 alpha 和 beta 之间；
- 每次对于当前 node，进入下层递归时，如果进入 node.left, 则更新 beta 为
node.val，若进入 node.right, 则更新 alpha 为node.val；
总结： 这种解法的 code 最为简单，逻辑也很清晰，个人认为目前而言这种方法是最好的, 其次是iteratively的inorder traversal 沿途判断递增，再其次是递归函数返回 boolean 和 子树的min/max value；
Java Code:
class Solution {
public boolean isValidBST(TreeNode root) {
return helper(root, (long)Integer.MIN_VALUE - 1, (long)Integer.MAX_VALUE + 1);
}
// 每次检查当前root.val是否在 alpha和beta之间，alpha为lower bound， beta 为 upper bound
private boolean helper(TreeNode root, long alpha, long beta) {
if (root == null) return true;
if (root.val <= alpha || root.val >= beta) return false;
return helper(root.left, alpha, root.val) && helper(root.right, root.val, beta);
}
}