给定一棵树 T 和一系列节点 S，对 S 的唯一限制是它是通过某种类型的递归完成的——也就是说，如果一个节点的所有祖先都已经出现，那么它只能出现在 S 中，什么是好的算法确定 S 是广度优先访问、深度优先访问还是两者都不是？
蛮力方法是计算每个广度优先和深度优先序列，看看是否有任何与 S 相同的序列。有更好的方法吗？
如果我们不想要一个是或否的答案，而是一个距离的度量怎么办？
更新 1通过距离测量，我的意思是访问可能不是精确的 BFS，但它很接近（一些编辑可能会使其成为一个）；我希望能够订购它们并说 BFS < S < R < U < DFS。
更新 2当然，每个 BFS 或 DFS 的暴力枚举都可以回答这个问题；我想要更有效的东西。
你有树和序列，对吧？在这种情况下，很容易确定一个序列是否是广度优先搜索，以及它是否是深度优先。
首先检查是否是广度：将节点分成L0，L1，...，Lk组，其中L0是0级节点的集合（只有一个根节点，所以它的大小为1），L2是集合1 级节点等。如果序列 S = (permutation(L0), permutation(1), ...) 那么它是广度优先搜索。
要检查它是否是深度优先：从指向树的序列中的第一个节点和根节点的指针开始。他们应该是一样的。如果前一个节点有任何子节点，则序列的下一个元素必须是前一个节点的子节点。如果存在冲突，则它不是 DFS 序列。如果没有子节点，则下一个序列元素必须是前一个节点的父节点的子节点，......等等。这种方法并不像听起来那么复杂，并且可以在堆栈的帮助下轻松实现。
我不太确定您是否需要“测量距离”。但是正如你所看到的，这两种方法都可以返回冲突的数量。也许你可以用它来计算“距离”？