检查一棵树是否是 BST

Question

这是我检查一棵树是否是 BST 的尝试：

public boolean isBST() {
    return isBSTRecursively(this.root, new Max());
}

class Max {
    int value;
}

private boolean isBSTRecursively(Node node, Max max) {
    if (node == null) return true; // to handle null root
  
    // to handle scenario when both child nodes are absent
    if(node.getLeft() == null && node.getRight() == null) {
        max.value = node.getValue();
        return true;
    }

    // if left child is absent, we only investigate right subtree
    if(node.getLeft() == null) {
        Max rightMax = new Max();
        boolean isRightBST = isBSTRecursively(node.getRight(), rightMax);
        max.value = Math.max(node.getValue(), rightMax.value);
        if(isRightBST && node.getValue() < rightMax.value) {
            return true;
        } else {
            return false;
        }
    } else {
        Max leftMax = new Max();
        boolean isLeftBST = isBSTRecursively(node.getLeft(), leftMax);
        // if right child is absent, we only investigate left subtree
        if(node.getRight() == null) {
            max.value = Math.max(node.getValue(), leftMax.value);
            if(isLeftBST && node.getValue() > leftMax.value) {
                return true;
            } else {
                return false;
            }
        } else {
            // we investigate both left and right subtrees
            Max rightMax = new Max();
            boolean isRightBST = isBSTRecursively(node.getRight(), rightMax);
            max.value = Math.max(Math.max(leftMax.value, node.getValue()), rightMax.value);
            if(isLeftBST && isRightBST && leftMax.value < node.getValue() && node.getValue() < rightMax.value) {
                return true;
            } else {
                return false;
            }
        }
    }

经多个测试用例测试，代码工作正常。

但我不确定这是否是一个好的、干净的方法。

递归方法看起来很大。我正在分别处理诸如左节点为空、右节点为空、节点本身为空、两个子节点为空等场景。我想它们都可以以更小、更干净的方式处理。

此外，我总是更倾向于迭代方法（我通常发现它更好地可视化）。在这里会更好吗（假设它可以迭代完成）？

有什么建议吗？

Answer 1

更简洁的递归方法

您可以使用有界方法，即每个递归都有两个变量：min 和max。

• 最初min = INT_MIN和max = INT_MAX

• if node = NULL then return True 因为空 BST 是 BST

• 否则检查 node.val min 或 node.val > max 如果此条件为 True 则树不是 BST，返回 False 注意：严格不等式 > 和 < 被使用，因为 BST 不允许重复元素。

  


• 左递归：recur(node.left)，其中 min 保持不变，并且 max = node.val - 1 因为左子树的值不应大于 node.val - 1。

  max 不能是 node.val，因为 BST 不能有重复元素。
  将布尔返回值存储在 left

  中

• recurse for right 中：recur(node.right) with min = node.val + 1和 max 保持不变。

  右子树的值应不小于node.val + 1。
  将布尔返回值存储在 right

  中

• return left && 中正确

Answer 2

@Aditya 给出了更优雅的解决方案的成分。

通常不禁止二叉搜索树具有重复值，因此不应将“窗口”减少1。

以下是建议代码：

public boolean isBST() {
    return isBSTRecursively(this.root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private boolean isBSTRecursively(Node node, int min, int max) {
    return node == null
           || node.getValue() >= min && node.getValue() <= max
               && isBSTRecursively(node.getLeft(), min, node.getValue())
               && isBSTRecursively(node.getRight(), node.getValue(), max);           
}