树遍历与递归概念题

Question

许多大小为 N 的问题的递归解决方案都遵循以下模式：

第 1 步：求解最小输入（例如，n = 1）的问题

第 2 步：给定大小为 n = k-1 (k <= N) 的相同问题的解决方案，求解 n = k。

我们可以看出这里的归纳性质，这就是为什么我们通常使用归纳来证明递归算法。对于某些问题，例如递归斐波那契数列，这种模式以明显的方式出现。我的问题是，比方说，二叉树遍历是否也可以被视为遵循这种模式？

以深度优先搜索为例：

def DFS(root):

  if root == None:
    return
  print(root.value)
  DFS(root.left)
  DFS(root.right)

我了解代码和调用堆栈，但我很难准确阐明步骤 1 和步骤 2 对 DFS 的意义（保持上述递归解决方案的结构）。不可能只有当前节点为None时才是base case，因为遍历单个节点也应该是base case

如果我说第 4 行，即包含 print 语句的那一行，是一个基本情况，那将没有多大意义，因为它针对每个子树运行。

Answer 1

它遵循相同的模式。

要解决的“问题”是以正确的顺序打印树。您的代码实现了预购。

Step 1: Solve the problem for the smallest input (say, n = 1)

这里最小的问题是打印空树 (root is None)。在这种情况下，解决方案是不打印任何内容（仅 return）。

Step 2: Given the solution to the same problem of size n = k-1 (k <= N), solve it for n = k.

我们可以认为k表示当前树的节点数，n表示这棵树的直接子树的节点数。打印左子树或右子树是一个较小的问题，其中 n <= k-1（注意 <=）。

打印树（按预定顺序），包括打印根节点，然后解决左右子树的“问题”。

一个区别是树的输出是这个函数的“副作用”——它不是 return 结果，而是输出它。这意味着进行递归调用的人不需要取回结果即可使用。一个更纯粹的函数将 return 树的字符串表示形式，调用者将使用它与它正在构建的字符串连接，并将 return 给它自己的调用者。

Tree Traversal and Recursion Conceptual Question