15. 一个困难的信息流问题¶
有时，为控制递归函数而在树中上下传递正确的信息 会变得很复杂。 信息流本身相当简单，但决定传递什么 可能很棘手。
下面这个问题展示了一个更困难的例子。 给定一棵任意的二叉树，我们希望判定： 对于每个结点 \(A\) ，\(A\) 的左子树中 是否所有结点都小于 \(A\) 的值，以及 \(A\) 的 右子树中是否所有结点都大于 \(A\) 的值？ （这恰好就是二叉搜索树的定义。） 遗憾的是，要做出这一判定，我们需要知道一些 仅靠查看结点的父结点或子结点无法获得的上下文。
如 10.15.1 所示， 仅验证 \(A\) 的左子结点的值 小于 \(A\) 的值，以及 \(A\) 的右子结点 具有更大的值，是不够的。 验证 \(A\) 的值与其父结点的值一致 也不够。 事实上，我们需要知道某个给定结点 合法取值范围的有关信息。 该信息可能来自该结点的任意祖先。 因此，相关的范围信息必须沿树向下传递。 我们可以如下实现这个函数。
static boolean checkBST(BSTNode rt, int low, int high) {
if (rt == null) return true; // Empty subtree
int rootval = rt.value();
if ((rootval <= low) || (rootval > high))
return false; // Out of range
if (!checkBST(rt.left(), low, rootval))
return false; // Left side failed
return checkBST(rt.right(), rootval, high);
}
static <E extends Comparable<E>> boolean checkBST(BSTNode<E> rt, E low, E high) {
if (rt == null) { return true; } // Empty subtree
E rootval = rt.value();
if ((rootval.compareTo(low) <= 0) || (rootval.compareTo(high) > 0)) {
return false; // Out of range
}
if (!checkBST(rt.left(), low, rootval)) {
return false; // Left side failed
}
return checkBST(rt.right(), rootval, high);
}
