c - 如何在 C 中实现打印树的所有路径的功能？

Question

我尝试编写一个函数来打印从根节点到叶节点的所有路径。

• 按照从根到叶的顺序打印节点
• 对于每个节点，左 child 都在右 child 之前
• 在节点值之后加上空格，包括最后一个
• 以换行符结束每条路径，包括最后一条
• 如果 root 为 NULL，则不打印任何内容

例如；

printPaths(bt1);
>2_1_
>2_3_

对于这个例子，2 是根，1-3 是叶。

这是我的简单代码，我找不到换行的地方，因为当我在任何地方写 printf("\n") 时，它都会打印疯狂的输出，所以我找不到问题所在这段代码。

void printPaths(TreeNode* root) {

    if(root != NULL) {
        printf("%d ", root->val);
        printPaths(root->left);
        printPaths(root->right);
    }

}

Answer 1

你需要在“每条路径的末尾”换行，所以当你到达一片叶子时:

if (root->left == NULL && root->right == NULL)
    printf("\n");

但是，您将无法使用代码再次打印整个路径，您需要在访问树时跟踪路径并在到达叶子时打印路径:

void printPaths(TreeNode* root, int path[], int len)
{
  if (root == NULL) // if the root is NULL, do not print anything
    return;

  path[len++] = root->val; // add root to your path

  if (root->left == NULL && root->right == NULL) // we reached a leaf
    printPath(path, len); // print the path we followed to reach this leaf
  else
  {
    printPaths(root->left, path, len);
    printPaths(root->right, path, len);
  }
}

void printPath(int path[], int len)
{
  for (int i = 0; i < len; i++)
    printf("%d ", path[i]);
  printf("\n");
}