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

Question

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

树的分支是从根到叶的路径,分支到特定叶的长度是从根到该叶的路径上的弧的数量.

设MinBranch(l,r,x)是一个简单的递归算法,用于将由l和r函数编码的二叉树与用于二叉树的根节点x一起,并返回二叉树的最短分支.

请提供此算法的伪代码.

Answer 1

我看到你已经收到了关于如何获得最短分支长度的答案,但你的家庭作业实际上是返回分支本身,可能是一个节点列表.所以,这里是可执行的伪代码(即Python)实际返回分支,None用于表示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