9.7. 递归函数中的信息流¶
9.7.1. 递归函数中的信息流¶
在递归函数中处理信息流可能颇具挑战。对任意一个函数，我们可能需要关注以下两种情况之一或两者：
向下传递函数完成其工作所需的正确信息，
把信息返回（向上传递）给递归函数的调用者。
任何给定问题都可能需要做其中一件或两件。下面是一些示例和练习。
9.7.1.1. 局部¶
局部遍历是指走到树中的每个结点去执行某种操作。这类函数不需要来自父结点的信息（除了指向当前结点的指针），也不返回任何信息。例子包括前序遍历，以及把每个结点的值加一。
9.7.1.2. 向下传递信息¶
稍微复杂一点的情形是，每个结点都需要被传递同一份信息。一个例子是把所有结点的值都增加某个量。这种情况下，值参数在所有递归调用中都原样向下传递。
许多函数需要逐结点变化的信息。一个简单的例子是，把树中每个结点的值设置为其深度。这种情况下，深度作为参数传递给函数，而每次递归调用都必须调整该值（加一）。
9.7.2. 二叉树设置深度练习¶
9.7.3. 收集并返回¶
收集并返回要求我们把信息沿树向上回传给调用者。简单的例子是统计树中结点的个数，或者对所有结点的值求和。
当你编写一个返回值的递归函数时，例如统计子树中结点的个数，你必须确保函数确实返回了值。一个常见的错误是进行了递归调用却没有捕获返回值。另一个常见的错误是没有返回值。
9.7.4. 二叉树校验和练习¶
9.7.5. 二叉树叶结点计数练习¶
9.7.6. 二叉树结点求和练习¶
9.7.7. 组合信息流¶
许多函数既要求传入信息，又要求返回信息。让我们从一个相对简单的情形开始。如果我们想检查树中是否有某个结点具有特定值，那么该值必须向下传递，而计数必须向上返回。向下流动很简单，因为被检查的值从不改变。向上传递的信息采用简单的收集并返回风格：当且仅当某个子结点返回 True 时才返回 True。
9.7.8. 二叉树检查值练习¶
9.7.9. 组合问题¶
稍微复杂一些的问题会结合我们目前所看到的内容。沿树向下传递的信息逐结点变化。沿树向上返回的数据采用收集并返回范式。
