algorithm - 返回二叉树中最短分支长度的算法

Question

可以使用两个函数 l 和 r 对二叉树进行编码，使得对于节点 n，l(n) 给出 n 的左孩子，r(n) 给出 n 的右孩子。

树的分支是从根到叶子的路径，分支到特定叶子的长度是从根到该叶子的路径上的弧数。

令 MinBranch(l,r,x) 是一个简单的递归算法，用于获取由 l 和 r 函数编码的二叉树以及二叉树的根节点 x，并返回二叉树的最短分支。

请提供此算法的伪代码。

Answer 1

我看到你已经收到了关于如何获得最短分支长度的答案，但你的家庭作业实际上是返回分支本身，大概是一个节点列表。因此，这里是实际返回分支的可执行伪代码（即 Python），使用Noneto 表示 null：

def MinBranch(l, r, x):
  if x is None: return []
  left_one = MinBranch(l, r, l(x))
  right_one = MinBranch(l, r, r(x))
  if len(left_one) < len(right_one):
    tail = left_one
  else:
    tail = right_one
  return [x] + tail

Answer 2

看看两个分支。找出每个中最短路径的长度。将较小的加一并认为它是最短的分支。

Answer 3

您也可以在 O(2 ^R ) 中找到它，其中 R 是结果。如果树非常不平衡或无限，则很有用。它是 <= O(N)。

您可以通过迭代深化 DFS 来做到这一点。

Answer 4

function recurseMin(n)
{
if r(n) is null and l(n) is null, return 1
if r(n) is not null, rightSum = recurseMin( r(n-1) )
if l(n) is not null, leftSum = recurseMin ( l(n-1) )
return 1 + min( leftSum, rightSum )
}