各ノードが値を持つことができる二分木があります。
ツリー内で値がnullで、ルートに最も近いノードを見つけたいと思います。ルートから同じ距離にある2つのノードがある場合は、どちらでもかまいません。二分木への読み取りアクセスの数を最小限に抑える必要があります。作業メモリーがkノードのみに制限されていると想定します。
深さkまでのDFSは網羅的ですが、最初にツリー全体を実行しない限り、最も近いノードは見つかりません。BFSは最も近いものを見つけますが、DFSは同じメモリでより深いヌルを見つけることができるため、失敗する可能性があります。
ツリーへの読み取りアクセスの数を最小限に抑えて、最も近いnullノードを見つけたいと思います。
（最終的にはこれをn-wayツリーにも実装する必要があるため、一般的な解決策が適切です。ツリーへの書き込みアクセスはなく、読み取りのみです。）
単純なツリープルーニングを使用してDFSを実装します。したがって、ツリー全体を実行する必要があるというのは真実ではありません。
たとえば、高さhにnull値を見つけた場合、同じ位置またはより深い位置にあるノードをスキップできます。
反復深化深さ優先探索を確認することをお勧めします。最も近いノードが自動的に検出されますが、DFSと同じ深さに到達できます。ただし、より多くの読み取りアクセスを使用します。
BFSから始めることもできます。許可されたメモリでヌルが見つからない場合は、DFSを実行します。
データ構造を変更できない場合は、幅優先で各ノードを読み取る必要があります。
データ構造を変更できる場合、各ノードは最初のnull子ノードの相対的な深さを記録できます。（それぞれの子の同等の値から計算します）。
次に、最も早いnullを探すときに、ツリー内のどの行を追跡するかがわかります。
ツリーを配列に格納したい場合は、簡単な方法があります。各ノードがその左右の子へのポインタを持つのではなく、ノード n の子は配列内で 2n + 1 と 2n + 2 です。(そして、n != 0 の場合、ノード n の親は (n-1)/2 です。)
Node tree[] = { 0, //root
1, // root's left child
2, // root's right child
3, // 1's left child
4, // 1's right child
5, // 2's left child
6, // 2's right child
...,
};
配列を単純に線形に反復することは BFS と同等ですが、必要なスペースは O(1) です。
これは n 分木に簡単に拡張できます。たとえば、三分木では、n !=0 の場合、左の子は 3n+1、中央は 3n+2、右は 3n+3、親は (n-1)/3 です。