Edit the question to include desired behavior, a specific problem or error, and the shortest code necessary to reproduce the problem. This will help others answer the question.
Closed 4 years ago.
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
接受
或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论(2)
我想我已经掌握了窍门。但我并不假装它很有效率。
让我们看看 BFS 输出的前 3 位数字:
我们处于以下情况之一:
这 2 种情况的 DFS 是多少?
快速说明:如果
3
没有任何子级,那么就不可能区分这两个...如果我们认为问题是可判定的,那么就需要知道 DFS 表示中
5
是否位于3
之后。4
有 2 个子级3
和5
,您可以轻松识别来自 DFS 表示的子树。然后从你拥有的 BFS 中提取(保留顺序)这些子树的 BFS 表示并递归:)这似乎离最佳状态还很远,但我更担心不确定性。
表达式解析树中是否存在一个约束,即一旦您有一个只有一个子节点的节点,它所代表的子树中的所有节点都不能拥有多个子节点?
I think I have the hang of it. I don't pretend it's efficient though.
Let's look at the first 3 digits of the BFS output:
We are in one of these situations:
What is the DFS for those 2 cases ?
Quick note: if
3
does not have any child, then it's impossible to tell the two apart...If we consider that the problem is decidable, then it's a matter of knowing if
5
follows3
in the DFS representation.4
has 2 children3
and5
and you can easily identify the subtree from the DFS representation. Then extract (preserving order) the BFS representation of these subtrees from the BFS you had and recurse :)It seems fairly far from optimal, but I am a bit more worried about the undecidability.
Is there a constraint in expression-parse trees which states that once you have a node that only has one child none of the nodes in the subtree it represents can have more than one ?