如何实现在C中打印树的所有路径的函数？

Question

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

• 按从根到叶的顺序打印节点

例如

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");
}