问题标签 [inorder]

我的输入结果24, 4, 2, 3, 9, 10, 32，我得到以下结果2, 3, 4, 24。

我正在使用堆栈。else if当我手动检查该程序时，即使有正确的子树，节点也不会在堆栈上的 4 处通过。

我对不同站点上的许多文章感到非常困惑，这些文章涉及Binary Search Tree从任何一个遍历（pre，post或in-order）或其中任何两个的组合构建一个。例如，在这个页面上，它说给定pre,post或level顺序遍历，连同in-order遍历，可以构造BST. 但是在这里和那里，他们向我们展示了如何单独构建一个BST。pre-order此外，他们在这里向我们展示了如何构造BSTfrom givenpre和post-ordertraversals。在其他一些站点中，我找到了一个BST仅从post-order遍历构造 a 的解决方案。

现在我知道给定inorder和pre-order遍历，可以唯一地形成一个BST. 至于我提供的第一个链接，虽然他们说我们不能构造BSTfrompre-order和post-order，但我不能对post-order数组进行排序以获取它的inorder遍历，然后使用它和pre-order数组来形成BST? 这与第四个链接中的解决方案相同还是不同？并且pre-order仅给出，我可以对它进行排序以获得in-order，然后使用它和pre-order来获得BST. 同样，这是否必须与链接 2 和 3 的解决方案不同？

具体来说，什么足以唯一地生成BST？如果不需要唯一性，那么我可以简单地对其进行排序以获取遍历，并从中递归地in-order构建 N 个可能的 s 之一。BST

给定一个二叉搜索树，例如：

我想获得一个有序的节点列表，其值在 a 和 b 之间（包括）。

我已经实现了一个递归辅助函数：

这给了我：

但是我需要：

反正有没有扁平化列表？我意识到我正在做的是将一个列表附加到另一个列表，但我不确定如何在不破坏代码的情况下解决这个问题。

我知道当给定二叉树的中序和前序遍历作为字符串时，您可以重建二叉树，但是仅在给定中序遍历的情况下，是否可以找到后序和/或前序遍历？

使用 int 的二叉搜索树创建一个包含小于给定整数x值的所有整数的链表。

我试过什么？

1）残酷的解决方案（低效）

BST的 有序访问，我在列表中为Bst中的每个整数插入一个节点，然后我从x开始释放列表的每个节点

2）更高效但错误

我进行了搜索，当我找到 x 时，我创建了一个列表，其中包含对我找到 x 的节点的左儿子的有序访问。

这显然是错误的，例如考虑以下 BST：

使用此解决方案，如果 x=15 我只考虑 {12,13,14}，它只适用于 x=root。

问题是我该怎么办？

在去面试之前我正在做一些准备工作，我刚刚了解了 Morris Traversal。

这是我用 Java 编写的 Morris Traversal 代码（它的工作）：

这是我的 In-Order 方法的代码：

我主要做的是：我在我的二叉树中插入了 70,000,000 个节点，然后我做了下一个小检查：

结果让我吃惊！

这些是结果：

莫里斯遍历 TOOK：637 毫秒

递归有序 TOOK：367 毫秒

注意 - 当我做这个测试时，我评论了来自 morrisTraversal() 和 recInOrderHelper() 方法的所有 System.out.println(...) 。

这些结果让我感到惊讶，因为我认为 Morris Traversal 会更快，因为它的迭代（不打开堆栈帧等）和 In-Order 是递归的（每次递归调用打开大约 70,000,000 个堆栈帧）

我知道它们都是 O(n)，所以显然我对某些事情是错误的，但是哪个？我错过了什么？为什么 Morris Traversal 比递归 In-Order 慢得多？

编辑-我还进行了下一个测试：我没有向树中插入 70,000,000 个节点，而是插入了 100,000 个节点并且我确实运行了下一个代码：

结果是：

递归有序 TOOK：214434 毫秒

莫里斯遍历 TOOK：502786 毫秒

正如您所看到的，与递归 In-Order 相比，Morris Traversal 仍然非常慢。所以我又做了一次测试，只插入了 1000 个节点，每个代码只运行了 10000 次，结果是：

递归有序 TOOK：44 毫秒

莫里斯遍历 TOOK：97 毫秒

我还是不明白？为什么莫里斯遍历速度较慢？

首先，我想说这不是家庭作业。我正在准备面试并遇到这个问题。我想我们可以传递中序和水平序遍历的定义。:-)。

例如：

上述树的中序和层序遍历为：

5、10、20、50、51、55、60、65、70、80

50, 10, 60, 5, 20, 55, 70, 51, 65, 80

我的想法：

(1) 遍历层序数组，找出出现在有序数组中的第一个元素。我们将此元素称为当前根。

(2) 在有序数组中找到当前根的索引。有序数组由索引分隔。有序数组的左边是当前根的左子树，有序数组的右边是当前根的右子树。

(3) 将有序数组更新为其左侧，然后转到步骤 1。

(4) 将有序数组更新为其右侧，然后转到步骤 2。

以上面的树为例。

谁能帮我验证我的解决方案？如果再给一个，真的很感激。

我正在尝试使用中序遍历（在 java 中）打印出二叉树，但没有任何歧义。

我从后序符号输入创建了树。

例如，输入 = 2 3 4 * - 5 + 然后我创建树，并希望使用中序遍历将其打印出来。

所以输出必须是 = 2 - (3*4) + 5 但是，使用按顺序遍历显然不会给我分隔括号。

我的问题是，我可以按我想要的方式打印输出，而无需干预基本的 BinaryNode 和 BinaryTree 类，而只更改我的驱动程序类吗？如果是这样，我将如何去做？

如果我只能通过更改我的 printInOrder 方法（在 BinaryNode 类中）来做到这一点，这就是它目前的样子：

这是我第一次使用 Stack Overflow，如果我没有正确发布，请放轻松:)

如何为以下树结构展平树（中序遍历）：https ://gist.github.com/damadamdam/7b6364220b11871f2930

我的预期答案也附在要点中。

我试图熟悉在给定中序和后序遍历的情况下创建树的问题。我编写了以下代码，但有些事情出了问题，我无法找出。有人可以帮我吗？

样本 i/p ：

int in[] = {4,10,3,1,7,11,8,2}; int post[] = {4,1,3,10,11,8,2,7};