检查一棵树是否是二叉搜索树

我无法理解Java函数HERE（请滚动到页面的最后）如何检查树是否为BST，因为代码看起来不像是使用最小和最大。我这里复制粘贴代码以及检查一棵树是否是二叉搜索树

/** 
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); 
    } 
}

来源

2014-11-22 Andy897

代码isBST2（）方法：P。这只是检查最小最大条件是错过了。 – Andy897 2014-11-22 13:51:17

“一个更好的解决方案只查看每个节点一次，诀窍是编写一个实用辅助函数isBSTRecur（struct node * node，int min，int max），它遍历树中的最小和最大允许值，它看起来每个节点只有一次，最小值和最大值的初始值应该是INT_MIN和INT_MAX--它们从那里缩小。“ – DavidPostill 2014-11-22 13:52:52

@DavidPostill虽然这里的语法是C，但不是Java。 – 2014-11-22 13:55:45

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

这正是你的代码差不多。它检查一棵树是给定最小值的给定最小值的BST。它通过查看具有值数据的根节点来递归调用自身，然后检查左侧分支是否为BST，其中任何节点都不超过数据，并且右侧分支是BST，节点小于数据。

但实际上它并没有完全做到这一点......它错过了最小/最大检查！也许你应该自己补充一下？这是功课吗？

的地方加入它会在这里：

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

你只需要如果node!=null一些额外的条件......

来源

2014-11-22 13:52:18

哪里是检查“谁的节点都不超过数据，并且右边的分支是BST，其节点都小于数据的节点”的代码。 – Andy897 2014-11-22 13:53:14

@ Andy897对不起，这是我在编辑时发布的危险......它没有那么做。我猜你应该添加它。 – 2014-11-22 13:54:04

哈哈。不，我太老了，不能做家务。 :) ..我在斯坦福*网站上找到了这个。：P链接在帖子中分享 – Andy897 2014-11-22 13:54:22

检查一棵树是否是二叉搜索树

回答

相关问题