java - 检查二叉树是否是 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;
}

我理解中序遍历，并且理解比较当前节点的左子节点以确保它 <= 与 n.data <= last_printed 行中的父节点，但是在这个递归中我们在哪里检查是否右子项大于父项？

Answer 1

右子节点的检查方式和位置与左子节点相同。

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

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