问题标签 [preorder]

我们知道二叉树的给定的前序和中序遍历唯一地定义了这棵树，那么一般的树，即具有两个以上孩子的树，前序和中序遍历是否与树结构一一对应。

换句话说，给定一个通用树的元组 (preorder,inorder) 它对于通用树是唯一的，还是可以有许多树具有相同的 preorder 和 inorder 遍历元组？

我们都熟悉二叉树的前序、中序和后序遍历。数据结构类中的一个常见问题是：

• 当给定中序和后序遍历时，找到二叉树的前序遍历。
• 或者，您可以在给定中序和预序时找到后序遍历。
• 但是，一般来说，当给定树的前序和后序遍历时，您无法确定树的中序遍历。

我想知道为什么，有没有一种从理论上解释它的好方法？

更新 1 一个答案：父母只有 1 个孩子的叶子会有问题，因为在这种情况下，这样的叶子可以是左孩子或右孩子。

这是第 2 轮亚马逊面试问题。将给定的二叉搜索树转换为预购和后购链表，并且必须进行这种转换。

我正在尝试解决这个问题https://oj.leetcode.com/problems/binary-tree-preorder-traversal/，即使用递归解决方案进行前序遍历。

编辑：整个代码：

由于以下原因，我有错误的答案：

有人可以告诉我如何解决这个问题吗？

编辑：我没有main()方法或单元测试。如果您打开我发布的链接，您会看到这是在线评审系统。

试图围绕如何更正我的代码。我有这个想法，但我在实施过程中陷入困境。

当我单步执行下面的代码时，我可以从预购遍历中重建 BST 的一部分。但在某些时候，我会有这样的函数调用：

这导致未分配叶子。我还不知道如何纠正这个问题。

我已经看到有关此主题的其他线程，但想解决我的问题，以便我可以真正了解重建 BST 的概念。

我有两棵二叉树，节点的值不需要不同。我想确定一棵树是否是另一棵树的子树。

比较两棵树的前序遍历与空节点的字符串是否足以和必要（iff条件）来确定一棵树是否是另一棵树的子树？

例如，

A.左 = B

预购：A、B、null、null、null

A.正确 = B

预购：A，空，B，空，空

我试图确保我理解这里隐藏的假设是什么。

这里的代码给出了正确的结果。

正如预期的那样，输出是abcdef

有人可以证实我的怀疑，这仅是因为两件事：

1. struct 成员在 n 字节边界处对齐（n ！= 1）（n = 4，似乎，在询问 sizeof()-s 时）
2. 第一个成员（即 a char）在 n 字节边界之前未使用的字节被归零。

我看不到 printf 正常工作的其他解释，因为它需要一个以零结尾的 char[]。

此外，这样做是否明智（在单目标嵌入式代码情况之外，优化可能超过可读性和可移植性问题），即。这些假设或多或少普遍正确吗？

第一周间歇性地弄乱 C，所以我很绿。

我无法让我的代码对树进行预排序遍历到列表才能工作。树的定义如下：

我对前序遍历的定义如下：

但是我得到的错误是：

我知道我的问题是该函数的第一个参数的类型以及它需要如何成为 [c] 类型，但我一生无法弄清楚如何得到它。我已经尝试了 fa 周围的所有括号组合，没有括号，没有一个让我成功运行。

我正在尝试使用前序遍历在由字符 az 和 AZ 组成的二叉树中找到一个节点，其中向左标记为“0”，向右标记为“1”，以便正确对于左侧两个分支的节点，输出看起来像“00”。节点未排序。

到目前为止，我有这个：

输出表明我正在到达正确的节点，但它不打印路径。

对于树的 PreOrder 遍历，我有这个 Prolog 谓词：

问题是，它返回一个不完整的列表。例如，我得到：

什么时候应该L=[1,2,3,4,5]。

为什么会短暂停顿？