7. 递归函数中的信息流¶

7.1. 递归函数中的信息流¶

在递归函数中处理信息流可能颇具挑战。对任意一个函数，我们可能需要关注以下两种情况之一或两者：

向下传递函数完成其工作所需的正确信息，
把信息返回（向上传递）给递归函数的调用者。

任何给定问题都可能需要做其中一件或两件。下面是一些示例和练习。

7.1.1. 局部¶

局部遍历是指走到树中的每个结点去执行某种操作。这类函数不需要来自父结点的信息（除了指向当前结点的指针），也不返回任何信息。例子包括前序遍历，以及把每个结点的值加一。

7.1.2. 向下传递信息¶

稍微复杂一点的情形是，每个结点都需要被传递同一份信息。一个例子是把所有结点的值都增加某个量。这种情况下，值参数在所有递归调用中都原样向下传递。

许多函数需要逐结点变化的信息。一个简单的例子是，把树中每个结点的值设置为其深度。这种情况下，深度作为参数传递给函数，而每次递归调用都必须调整该值（加一）。

7.2. 二叉树设置深度练习¶

7.3. 收集并返回¶

收集并返回要求我们把信息沿树向上回传给调用者。简单的例子是统计树中结点的个数，或者对所有结点的值求和。

Example 7.7.1

考虑统计（并返回）一棵二叉树中结点个数的问题。关键洞见在于，任意（非空）子树的总数等于根结点的 1 加上左、右两棵子树的计数。左、右子树的计数从何而来？对子树调用函数 count 就能为我们算出这个值。于是，我们可以如下实现 count 。

Java
Java (Generic)

static int count(BinNode rt) {
  if (rt == null) return 0;  // Nothing to count
  return 1 + count(rt.left()) + count(rt.right());
}

static <E> int count(BinNode<E> rt) {
  if (rt == null) { return 0; }  // Nothing to count
  return 1 + count(rt.left()) + count(rt.right());
}

下面的解法是正确的，但效率不高，因为它对每个被访问结点的左、右子结点做了冗余检查。

static int ineff_count(BinNode root) {
  if (root == null) { return 0; }  // Nothing to count
  int count = 0;
  if (root.left() != null) {
    count = 1 + ineff_count(root.left());
  }
  if (root.right() != null) {
    count = 1 + ineff_count(root.right());
  }  
  if (root.left() == null && root.right() == null) {
    return 1;
  }
  return 1 + count;
}

当你编写一个返回值的递归函数时，例如统计子树中结点的个数，你必须确保函数确实返回了值。一个常见的错误是进行了递归调用却没有捕获返回值。另一个常见的错误是没有返回值。

Settings

Saving...

Server Error
Resubmit

7.4. 二叉树校验和练习¶

7.5. 二叉树叶结点计数练习¶

7.6. 二叉树结点求和练习¶

7.7. 组合信息流¶

许多函数既要求传入信息，又要求返回信息。让我们从一个相对简单的情形开始。如果我们想检查树中是否有某个结点具有特定值，那么该值必须向下传递，而计数必须向上返回。向下流动很简单，因为被检查的值从不改变。向上传递的信息采用简单的收集并返回风格：当且仅当某个子结点返回 True 时才返回 True。

7.8. 二叉树检查值练习¶

7.9. 组合问题¶

稍微复杂一些的问题会结合我们目前所看到的内容。沿树向下传递的信息逐结点变化。沿树向上返回的数据采用收集并返回范式。

CS3 数据结构与算法

Chapter 7 Binary Trees