检查二叉树是否是 BST

Question

我被下面的算法搞糊涂了：

public static boolean checkBST(TreeNode n) {
    if (n == null) {
        return true;
    }

    // Check / recurse left
    if (!checkBST(n.left)) {
        return false;
    }

    // Check current
    if (last_printed != null && n.data <= last_printed) {
        return false;
    }
    last_printed = n.data;

    // Check / recurse right
    if (!checkBST(n.right)) {
        return false;
    }
    return true;
}

我了解 in-order 遍历，并了解比较当前节点的左侧 child 以确保它 <= 与 [=16= 行中的 parent ] <= last_printed，但是在这个递归中我们在哪里检查右边的 child 是否大于 parent?

Answer 1

你的左方法和右方法是做什么的？你只是想验证你有一个二叉搜索树吗？

Answer 2

右侧 child 的检查方式和位置与左侧 child 相同。

该算法的工作原理就好像是通过 in-order 遍历打印每个节点的值，然后检查结果列表是否有序。然而，它并没有实际打印，而是在实例变量 last_printed 中维护本应在遍历的那个点上最近打印的值。无论遍历的进展和到当前节点的路径如何，标记为 // Check current 的测试都会正确测试当前节点是否按照与作为 BST 的树一致的顺序遍历。

需要注意的关键可能是 last_printed 在遍历当前节点时更新，在遍历左子树和右子树之间。

检查二叉树是否是 BST

Checking if binary tree is a BST

java

tree

recursion

graph