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

Question

A binary tree can be encoded using two functions l and r such that for a node n, l(n) give the left child of n , r(n) give the right child of n.

A branch of a tree is a path from the root to a leaf, the length of a branch to a particular leaf is the number of arcs on the path from the root to that leaf.

Let MinBranch(l,r,x) be a simple recursive algorithm for taking a binary tree encoded by the l and r functions together with the root node x for the binary tree and returns the shortest branch of the binary tree.

请提供该算法的伪代码。

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