验证二进制搜索树

Question

假设BST定义如下：

节点的左子树只包含键小于节点键的节点。节点的右子树只包含键大于节点键的节点。左子树和右子树也必须是二叉搜索树。

示例1：

                     2
                    / \
                   1   3

                     5
                    / \
                   1   4
                      / \
                     3   6

class Solution {
    public boolean isValidBST(TreeNode root) {
        
        return isValidHelper(root); 
    }
    
    public boolean isValidHelper(TreeNode root)
    {
        if(root == null)
            return true; 
        
        
        isValidHelper(root.left); 
        
 if(root.left != null && !(root.left.val < root.val) || root.right != null && !(root.right.val > root.val))
            return false; 
        
        isValidHelper(root.right); 
        
        return true;
    }
}

Answer 1

您的程序在以下情况下会失败：

     5
   3   7
  1 6

因为您只比较子树根部的值。

我不是故意给你一个答案。你会学到更多的发现自己。