问题标签 [non-recursive]

我需要实现一个前序遍历方法。遍历节点的二叉树。

我试图找出解决以下问题的方法。我知道如何实现这样的方法，但问题是我不能偏离老师给我的规则。这使得这项练习变得更加困难。

这些是规则：

• 老师禁止使用递归
• 我必须使用堆栈
• 从根节点开始

• 有关其他限制，请参阅我的代码中的注释。

  /li>

我希望有人可以帮助我解决这个问题。

我正在执行一项任务，我必须实现这两种方法（ add() 和 inOrder() ）。

下面的代码是我到目前为止所拥有的。我需要帮助的是调整代码以使其正常工作。目前，它没有做我想做的事。

add() 只会在树上添加最多 3 个级别，之后它只会更改第 3 级的节点。我不确定如何编写代码以使其超过 3 个级别。

inOrder() 不起作用。当我跑步时，它只是停下来，什么也不打印，迫使我停止跑步。

如果您需要更多信息，请与我们联系。

添加（）：

为了（）：

我正在努力解决这个问题，我想以非递归方式解决这个问题。我的算法似乎没有逻辑错误，73% 的测试用例通过了。但无法处理大数据，报“Time Limit Exceeded”。如果有人能给我一些提示，我很感激如何以非递归方式进行操作并避免超出时间限制，在此先感谢！

问题链接

我相信在 LeetCode 中也有类似的。

http://www.lintcode.com/en/problem/binary-tree-maximum-path-sum-ii/

问题描述：

给定一棵二叉树，找到从根开始的最大路径和。路径可以在树中的任何节点处结束，并且其中至少包含一个节点。

例子：

给定以下二叉树：

1

/ \

2 3

返回 4. (1->3)

法官

超过时间限制

总运行时间：1030 毫秒

输入 输入数据

{-790,-726,970,696,-266,-545,830,-866,669,-488,-122,260,116,521,-866,-480,-573,-926,88,733,#,#,483,-935,-285,-258,892,180,279 ,-935,675,2,596,5,50,830,-607,-212,663,25,-840,#,#,-333,754,#,817,842,-220,-269,9,-862,-78,-473,643,536,- 142,773,485,262,360,702,-661,244,-96,#,519,566,-893,-599,126,-314,160,358,159,#,#,-237,-522,-327,310,-506,462,-705,0,-945,-73,19,3 193,-205,-92,795,-99,-983,-658,-114,-706,987,292,#,234,-406,-993,-863,859,875,383,-729,-748,-258,329,431,-188,-375 ,-696,-856,825,-154,-398,-917,-70,105,819,-264,993,207,21,-102,50,569,-824,-604,895,-564,-361,110,-965,-11,557,#,202,213 ,-141,759,214,207,135,329,15,#,#,244,#,334,628,509,627,-737,-33,-339,-985,349,267,-505,-527,882,-352,-357,-630,782,23,-215,-555, 835,-421,751,0,-792,-575,-615,-690,718,248,882,-606,-53,157,750,862,#,940,160,47,-347,-101,-947,739,894,#,-658,-90,-277 ,-925,997,862,-481,-83,708,706,686,-542,485,517,-922,978,-464,-923,710,-691,168,-607,-888,-439,499,794,-601,435,-114,-337,422,#,-3,-859, 224,902,#,577,#,-386,272,-9 ...

预期的

6678

我的代码 C++

解决了

我接受了@Dave Galvin 的建议，它奏效了！这是代码：

您好，有人建议我学习非递归地编写东西，以便更清楚地了解程序中发生的事情。它是一个二进制搜索程序，它读取总统列表的 .dat 文件并按字母顺序对它们进行排序。这是我要使其成为非递归的代码：

我想了解什么是递归，以及如何看待递归的东西并使其成为非递归的。我很难理解这些概念。如果我使该部分非递归，我不确定是否需要调整二叉搜索树的其余部分。

这是完整的程序，以防您需要查看其他情况：

我试图把这个递归函数变成一个非递归函数。这是一个来自二叉搜索树的搜索函数。我知道让它递归是很自然的，但出于学习目的，我想让它成为非递归的。我怎么能这样做？提前致谢！

这是我在 Stack Overflow 上的第一篇文章。我真的很佩服这个网站和所有帮助其他人编写代码的用户。希望我能从你那里得到一些帮助:)

我遇到的问题可以描述如下：

1. 从给定节点（根节点）开始；
2. 计算节点的子节点并存储（计算前不知道子节点的个数）；
3. 在叶节点处，使用“评估函数”计算叶的值。
4. 当所有叶子都被评估后，选择具有最大/最小值的叶子节点，并获取存储在该叶子的祖父（根的孩子）中的数据，如图所示。

遍历并建树的过程：

由于“评估功能”只能应用于叶节点，我认为深度优先搜索适合这里。此外，Simulink 中的 MATLAB Function Block不支持递归调用函数。所以我认为使用Stack来存储节点是一个不错的方法。

根据这里的优秀答案，逻辑非常清晰和直接。来自Gumbo的代码

但是我在实现DFS算法的时候遇到了一些问题：

1. 由于邻接矩阵浪费大量内存，我尝试使用邻接表来表示树。但我什至没有找到使用邻接表实现 DFS 算法的伪代码。有人可以帮助我吗？

2. 从父节点（添加节点）计算新节点时如何更新树？

3. 我应该让孩子从祖父（root 的孩子）那里继承数据以节省追溯步骤吗？还有其他方法可以解决流程的第四步吗？

我正在用 Java 编写非递归合并排序算法我必须确保该方法是否作为非递归方法工作，并且空间复杂度应该是 O(N)

我得到的指令：您可以使用 O(N) 空间（除了输入数组）并且您的算法应该具有与递归合并排序相同的运行时间。

这是我的代码。

我想确保递归性以及 O(N) 空间如果有更好的方法，请告诉我。

我在为非递归 make 系统定义通用规则时遇到了困难。

背景

为了进一步阅读，而不是我复制太多现有材料，请参阅这个较早的问题，它很好地涵盖了基础，并且在构建这个系统时帮助了我。

对于我正在构建的make系统，我想定义系统组件之间的依赖关系-例如组件A依赖于组件B-然后离开make系统以确保构建B构建过程的任何产品之前构建需要它们A 的步骤。由于粒度的原因，这有点浪费（可能会构建一些不需要的中间体），但对于我的用例来说，它满足了易用性和构建性能之间的舒适平衡点。

系统必须处理的一个困难是无法控制 makefile 加载的顺序 - 实际上，这应该无关紧要。然而，正因为如此，在早期加载的 makefile 中定义的组件可能依赖于在尚未读取的 makefile 中定义的组件。

为了允许在所有定义组件的 makefile 中应用通用模式，每个组件都使用变量，例如：$(component_name)_SRC. 这是非递归（但递归包含）make 系统的常见解决方案。

有关 GNU make 不同类型变量的信息，请参阅手册。总而言之：简单扩展变量（SEV）随着生成文件的读取而扩展，表现出类似于命令式编程语言的行为；在读取所有 makefile 之后，递归扩展变量 (REV) 在 make 的第二阶段进行扩展。

问题

尝试将依赖组件列表转换为这些组件所代表的文件列表时会出现特定问题。

我已经将我的代码提炼成这个可运行的示例，它遗漏了真实系统的许多细节。我认为这很简单，可以在不失去其实质的情况下证明问题。

规则.mk：

生成文件：

这些将运行以提供：

hoge_a.txt 不包含在输出中，因为在foo_dependencies定义为 SEV 的hoge_src时候还不存在。

读取所有 makefile 后进行扩展是 REV 应该能够解决的问题，我之前曾尝试将其定义$(c)_dependencies_src为 REV，但这也不起作用，因为$(c)然后在替换时间而不是定义时间进行扩展，所以它不再保持正确的值。

如果有人想知道我为什么不使用特定于目标的变量，我担心将变量应用于手册中描述的目标的所有先决条件会导致不同组件的规则之间发生不必要的交互。

我想知道：

1. 这个具体问题有解决方案吗？（即有没有一种简单的方法可以使那条线达到我想要的效果？）
2. 有没有更典型的方式来构建这样的 make 系统？（即单个 make 实例，从多个 makefile 加载组件并定义这些组件之间的依赖关系。）
3. 如果有多种解决方案，它们之间的取舍是什么？

最后的评论：当我写下我的问题时，我已经开始意识到可能有一个解决方案可以使用 eval 来构造 REV 定义，但是因为我在 SO 上的其他任何地方都找不到这个问题，所以我认为值得为了未来的搜索者，无论如何都要问这个问题，另外我想听听更有经验的用户对此或任何其他方法的想法。

在Accelerated C++ Programming一书中，第 205 页，有以下两个实现find

我有兴趣了解以下两种实现在性能方面有什么区别（编译后是否实际上相同？）。

非递归的

递归的

通过使用Kerrek建议的编译器资源管理器，我得到了以下信息

非递归https://godbolt.org/g/waKUF2

递归https://godbolt.org/g/VKNnYZ

编译后好像一模一样？（如果我正确使用该工具..对不起，我对 C++ 很陌生）

我有一个项目，我想从递归转换为非递归 make。结构如下所示

我想要做的是在构建之后具有这样的结构

主要思想是构建文件夹包含所有对象和依赖文件，并且目标具有应加载的程序文件。

我遇到的问题是 make 永远不会想要创建这个结构。当我定义我的规则时，make 只会运行隐式规则而不是我定义的规则。

我已经阅读了关于非递归制作的所有资源，现在它还没有点击。任何帮助深表感谢。