验证二叉搜索树

来源Leetcode第98题验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

---

错误的思路

做的时候忘记判断当前结点的左子树数据是否大于上一结点的数据了，最终在第70/75个用例时出错

错误的代码:

public boolean isValidBST(TreeNode root) {

    if(root == null)
        return true;

    if(root.left == null && root.right == null)
        return true;

    if(root.left == null && root.right != null)
        return root.val< root.right.val && isValidBST(root.right);

    if(root.left != null && root.right == null)
        return root.val > root.left.val && isValidBST(root.left);

    return root.val > root.left.val && root.val< root.right.val && isValidBST(root.left) && isValidBST(root.right);
}

递归

来源题解
首先将结点的值与上界和下界（如果有）比较。然后，对左子树和右子树递归进行该过程。

 public boolean helper(TreeNode node, Integer lower, Integer upper) {
   if (node == null) return true;

   int val = node.val;
   if (lower != null && val <= lower) return false;
   if (upper != null && val >= upper) return false;

   //遍历右子树，当前结点的值放入lower
   if (! helper(node.right, val, upper)) return false;
//遍历左子树，当前结点的值放入upper
   if (! helper(node.left, lower, val)) return false;

   return true;
 }

 public boolean isValidBST(TreeNode root) {
   return helper(root, null, null);
 }

中序遍历迭代

利用中序遍历来判断是否是二叉搜索树

class Solution {
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode p = root;
        TreeNode pre = null;
        while (p != null || !stack.isEmpty()) {
		//先将左子树全部入栈
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
			//弹出最后一个左边结点
            p = stack.pop();
			//如果右子树的值比左子树的值小
			//直接返回false
            if (pre != null && pre.val >= p.val) return false;
            pre = p;
			//右子树入栈
            p = p.right;
        }
        return true;
    }
}

中序遍历递归

double last = -Double.MAX_VALUE;
public boolean isValidBST(BinaryTreeNode root) {
       if (root == null) {
           return true;
       }
       if (isValidBST(root.left)) {
           if (last < root.val) {
               last = root.val;
               return isValidBST(root.right);
           }
       }
       return false;
   }