反復ツリーに（存在する）ノードへのバイナリツリーやポインタを考えると、バイナリツリーに

Question

Example Tree image

をノードとその子を削除するには、私たちは親のポインタを持っていると仮定します。私は、削除されたノードの隣接ノードおよびそれに続く隣接ノードを削除する反復回数を見つけなければならない。ここでの削除とは、ノード→バーンのフラグを設定することを意味します。私はノードを削除しません。 例：

  1 
    / \ 
     2  3 
    /\ /\ 
    4 5 6 7 
//
    8 9 
/
10 

、ツリー内のノードを与えられたが4で、

反復1内の各反復

で焼かノード：

• ノード4について：4.8、 2（8は子ノード、2は4の親、これらは4の隣接ノードです）。反復2において

：ノード8について

• ：10が燃焼します。 （4は既に焼き付け済み）
• ノード2の場合：5と1が焼かれます。

これが続きます。したがって、すべてのノードを焼くのに必要な反復の回数を見つける必要があります。

Answer 1

ない効率的なが、私はそれがうまくいくと思う：

は削除のために考慮されるべき次のノードのキューを維持します。ノードの隣接ノードを削除する前に、すでにburnフラグが設定されているかどうかを確認してください。また

、あなたがキューから項目を削除するたび：

• チェックすべてのノードが（これのためにあなたがより速くアクセスのための Hashを維持することができる）燃えているかどう
• 増分反復回数（これはあなたの結果になります）