バイナリツリーは、ノードnに対してl（n）がn、r（n）の左の子を与えるように、 nの正しい子供を与える。バイナリツリー内の最短ブランチの長さを返すアルゴリズム
ツリーの分岐は、ルートからリーフまでのパスです。特定のリーフへの分岐の長さは、ルートからそのリーフまでのパス上の弧の数です。
MinBranch（l、r、x）は、バイナリツリーのルートノードxと共にlおよびr関数でエンコードされたバイナリツリーを取得する単純な再帰アルゴリズムであり、バイナリツリーの最短ブランチを返します。
このアルゴリズムの疑似コードを入力してください。
両方の分岐を見てください。それぞれの最短経路の長さを求める。小さいものに1を加え、それを最短の枝とみなします。
それは本質的にあなたのためのコードを書いています - ただ私がコードに書いたものを翻訳しようとします:) – bdonlan
rachel：itrueの擬似コードは多かれ少なかれbdonlanの答えと同じです、そしてAlex Martelliも同じアイデアを使います。それに続くのはちょっと難しいかもしれませんが、サンプルツリーを引き出し、3つの答えをすべて慎重に実行しようとします。途中でメモを取って迷子にならないようにしたいと思うかもしれません。うまくいけば、3人とも同じことをしていることが分かるでしょう（ブランチ自体と長さを区別する場合を除いて）。 – MatrixFrog
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)
}
recurseMin（）に引数があるようです... – hughdbrown
理由のために「編集」ボタンがあります。 3人の別々の人々がこれを訂正せずにアップボートすることは間違いありません。 –
また、1の数が多いようです。 3つのノード（ルート、左、右）を持つツリーがある場合は、3のカウントを取得すると思います。ルートは1 + min（leftSum、rightSum）です。 leftSumは1 + recurseMin（左）です。 recurseMin（左）は1です。rightSumは同じです。うん、3の深さ。 – hughdbrown
は、私はあなたが長さ最短枝の取得する方法についての答えを受けましたが、あなたの宿題はおそらくノードのリストとして、枝自体を返すために実際に参照してください。だから、ここ実行可能な擬似コード（すなわち、Pythonは）ヌルを意味するNoneを使用して、実際に支店を返すことだ：
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
ニース、アレックス。 – hughdbrown
@hugh、あなたがそれを気に入ってうれしくありがとう！ –
ます。また、Rは結果であるO（2 R）でそれを見つけることができます。ツリーが非常に不均衡または無限大の場合に役立ちます。 < = O（N）です。
これは反復深化DFSで行うことができます。
元の著者はそれを所有することに興味がないようなので、質問をwikiに変換しました。私の意見では、回答の一部は保存する価値があります。 –