检查树是否为 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
else 检查如果 node.val < min or node.val > max 如果这个条件是 True 那么树不是 BST，return False 注意：严格不等式 > 和< 被用作 BST 不允许重复的元素。
左递归：recur(node.left)，min 保持不变，max = node.val - 1 因为左子树的值不应大于 node.val - 1。

max不能是node.val因为BST不能有重复的元素。将布尔值 return 存储在 say left
中
右递归：recur(node.right) min = node.val + 1 和 max 保持不变。

右子树的值不应小于node.val + 1。将布尔值 return 存储在 say right
中
return left && right

Answer 2

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

二叉搜索树一般不禁止有重复值，所以应该不会把“window”减为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);           
}

检查树是否为 BST

Checking a tree to be a BST

java

algorithm

tree

binary-search-tree

data-structures