检查二叉树是否也是二叉搜索树的问题

我正试图解决这个问题，但我遇到了一些麻烦：

在二叉搜索树（BST）中：

• 节点左子树中每个节点的数据值小于该节点的数据值。
• 节点右子树中每个节点的数据值大于该节点的数据值。

给定根节点：

class Node { int data; Node left; Node right; } 

确定二叉树是否也是二叉搜索树

我有这个代码：

 boolean check(Node root) { //node doesn't have any children if (root.left == null && root.right == null) { return true; } boolean leftIsBst = true; boolean rightIsBst = true; if (root.left != null) { leftIsBst = (root.left.data  root.data) && check(root.right); } return leftIsBst && rightIsBst; } 

这在某些情况下有效，但在以下情况下失败：

如您所见，node （4）位于node （3）的左子树中，尽管4大于3，因此该方法应返回false 。 不过，我的代码返回true 。

我怎么能控制那个案子？ 如何检查左/右子树中的所有值是否低于/大于根（不仅仅是直接子）？

Answer 1

您的定义是正确的（尽管您不一定要坚持所有密钥都是不同的），但您的代码并未实现定义中的所有条件。 具体而言，您不会在每个子树中强制执行最小值和最大值。

这是一个有效的递归解决方案，可以实现您的定义：

 boolean check(Node root) { return check(root, INT_MIN, INT_MAX); } boolean check(Node n, int minval, int maxval) { if (n == null) { return true; } return ( n.data >= minval && n.data <= maxval && check(n.left, minval, n.data-1) && check(n.right, n.data+1, maxval) ); } 

请注意，我没有在n.data-1和n.data+1检查溢出，这在现实生活中你必须要做。 如果您想允许重复键，只需将它们更改为n.data ，您就不必担心它。

Answer 2

像下面这样的东西应该工作

 boolean check(Node root) { if (root == null) { return true; } if (root.left != null && max(root.left) > root.data ) { return false } if (root.right != null && max(root.right) < root.data ) { return false; } return check(root.left) && check(root.right); } 

注意：

• 这是相当低效的
• 你需要实现max()

Answer 3

您的递归逻辑不正确。 我在这里给cpp逻辑。 您可能需要将其转换为Java代码。

bool check（Node * root）{

 static Node *prev = NULL; if(root) { If(!check(root->left)) return false; If(prev != Null && prev->data > root->data) return false; Prev = root; return check(root->right); } return true; 

}

Answer 4

BST定义为：

– 节点的左子树始终包含值小于节点值的节点。 – 节点的右子树总是包含值大于节点值的节点。 – 左右子树也是有效的BST。

  class Solution { public boolean isValidBST(TreeNode root) { return helper (root,Integer.MIN_VALUE,Integer.MAX_VALUE); } public boolean helper(TreeNode root,long low,long high){ if (root==null){ return true; } if (root.valhigh){ return false; } return (helper(root.left,low,root.val-1) && helper(root.right,root.val+1,high)); } }