6.1.1. 基础情况¶

在二叉树遍历中，基础情况通常是检查是否遇到空树。 一个常见的错误是检查当前结点的子结点指针， 并且只对非空的子结点进行递归调用。

回顾基本的前序遍历函数。

static void preorder(BinNode rt) {
  if (rt == null) return; // Empty subtree - do nothing
  visit(rt);              // Process root node
  preorder(rt.left());    // Process all nodes in left
  preorder(rt.right());   // Process all nodes in right
}

static <E> void preorder(BinNode<E> rt) {
  if (rt == null) { return; } // Empty subtree - do nothing
  visit(rt);              // Process root node
  preorder(rt.left());    // Process all nodes in left
  preorder(rt.right());   // Process all nodes in right
}

下面是前序遍历的一种替代设计， 其中会检查当前结点的左、右指针， 以便只对非空子结点进行递归调用。

// This is a bad idea
static void preorder2(BinNode rt) {
  visit(rt);
  if (rt.left() != null) preorder2(rt.left());
  if (rt.right() != null) preorder2(rt.right());
}

// This is a bad idea
static <E> void preorder2(BinNode<E> rt) {
  visit(rt);
  if (rt.left() != null) { preorder2(rt.left()); }
  if (rt.right() != null) { preorder2(rt.right()); }
}

首先，它可能看起来像 preorder2 比 preorder 更高效，因为它只执行一半的递归调用（因为它不会尝试调用空指针）。另一方面， preorder2 必须访问左和右子指针的次数是两倍。最终结果是没有任何性能提升。

也许 preorder2 的作者想防止根结点为 null 的情况。 但 preorder2 有一个错误。 虽然 preorder2 确保不会对空子树进行递归调用， 但如果外部的最初调用传入空指针，它就会失败。 当原始树为空时就会出现这种情况。 由于空树是函数初始调用的合法输入， 因此没有安全的方法来避免这种情况。 所以在进行二叉树遍历时，你首先要做的就是检查根结点不是 null 。 如果我们试图通过添加这个测试来修正 preorder2 ， 那么对子结点所做的测试就完全是多余的， 因为在递归调用中会再次检查该指针。

preorder2 的设计比 preorder 差，还有一个更深层的原因。 查看子结点是否为 null ， 意味着我们过度担心了某些其实完全可以由子结点自己处理的事情。 这会使函数更复杂，对于更复杂的树结构来说，这可能成为真正的问题。 即使在相对简单的 preorder2 函数中， 我们也必须写两次对 null 的测试，而 preorder 只需要一次。 这使它比原来的版本更复杂。 关键在于，当我们只考虑当前结点的需求时， 编写作用于树的递归函数要容易得多。 只要可以，我们就希望让子结点自己照顾自己。 在这种情况下，我们关心的是当前结点不是 null ， 关心的是如何在子结点上调用递归， 但我们 不 必关心这是如何完成的、何时完成的。

6.1.2. 递归调用¶

编写递归函数成功的秘诀，就是不要担心递归调用是如何工作的。 只需接受它会正确工作这一事实。 这一原则的一个方面是：在不需要时不要操心去检查子结点。 只有当需要知道子结点的值才能计算当前结点的某个属性时， 你才应该查看子结点的值。 不应使用子结点的值来决定是否对它们进行递归调用。 进行调用，让它们自己的基础情况来处理。

在少数问题中，你可能需要显式检查子结点是否为空， 或者访问每个结点的子结点值。 例如，你可能需要检查树中的所有结点是否都满足 每个结点存储其左、右子结点之和这一性质。 在这种情况下，你必须查看子结点的值，才能对当前结点作出某种判断。 你 不 是通过查看子结点来决定是否进行递归调用。