java - 检查树是否是二叉搜索树

Question

我无法理解Java函数HERE (请滚动到页面的最后)检查树是否是 BST，因为代码看起来根本不像使用 min 和 max。我也将代码复制粘贴到此处

/** 
 Tests if a tree meets the conditions to be a 
 binary search tree (BST). Uses the efficient 
 recursive helper. 
*/ 
public boolean isBST2() { 
 return( isBST2(root, Integer.MIN_VALUE, Integer.MAX_VALUE) ); 
}
/** 
  Efficient BST helper -- Given a node, and min and max values, 
  recurs down the tree to verify that it is a BST, and that all 
  its nodes are within the min..max range. Works in O(n) time -- 
  visits each node only once. 
*/ 
private boolean isBST2(Node node, int min, int max) { 
  if (node==null) { 
    return(true); 
  } 
  else { 
   // left should be in range  min...node.data 
    boolean leftOk = isBST2(node.left, min, node.data);

    // if the left is not ok, bail out 
    if (!leftOk) return(false);

    // right should be in range node.data+1..max 
    boolean rightOk = isBST2(node.right, node.data+1, max);

    return(rightOk); 
  } 
} 

Answer 1

当且仅当中序遍历的节点是单调的时，树才是 BST。最简单的思考方法是，如果根的值为 n，那么左侧分支也应该是节点最多为 n 的 BST，右侧分支也应该是节点至少为 n 的 BST。如果满足这些条件，那么整个树就是 BST。

这正是您的代码几乎所做的。它检查一棵树是否是具有给定最小值和给定最大值的 BST。它通过查看具有值 data 的根节点来递归地调用自身，然后检查左侧分支是否是一个 BST，其节点均不超过 data，并且右侧分支是一个 BST，其节点均不小于 data。

但实际上它并没有完全做到这一点......它错过了最小/最大检查!也许您应该自己添加？这是作业吗？

添加它的位置在这里:

if (node==null) { 
  return(true); 
}

您只需要几个额外的条件 if node!=null...