[Leetcodeやるお]116. Populating Next Right Pointers in Each Node

スポンサーリンク




参照:https://leetcode.com/problems/populating-next-right-pointers-in-each-node/solution/

完全二分木があって、次の右ノードを指すように,各 next ポインタを生成する。
次の右ノードがない場合,次のポインタはNULLに設定される
初期状態では、すべての次のポインタはNULLに設定されています。

アプローチ

アプローチとして、これをIteratevely(繰り返し)で解いていきます。

・まずは各層で初期化するポインターを作ります。
・同じ階層の中で全ての子ノードに対してnextを修正していきます。
・各階層で一番右のノードはそれ以上右のノードを持たないのでNullをセットします。
・一つの階層で処理が終わったら下のレベルに移ります。

スポンサーリンク

解説

まずはポインターを作成します
Node leftNode = root;

NodeがNullでなく、下の階層が存在することを確認します。
while(leftNode != null & leftNode.left != null){

helperメソッドのpopulateLeftNode(leftNode)を呼び出し、下の階層へと移動します。
populateLeftNode(leftNode);

下の階層の処理が終わったら、ポインターをノードの左に移動させます。
leftNode = leftNode.left;

全ての処理が終わったらrootを返します。
return root;

ヘルパーメソッドについて。startNodeで各階層の一番左のノードを受け取ります。
private void populateLeftNode(Node startNode){

iterが一番左の階層がNullでないことを確認し、
while(iter != null){

iter.left.next = iter.right;
iterが2の時、4の次のポインターは5になります。

iterがnullでない=右端でない場合、
if(iter.next != null){

iter.right.next = iter.next.left;
iterが2の時、5の次のポインターは2の次の左、なので6になります。

ポインターを2の次に移します。
iter = iter.next;

と、まぁこんな感じ。つれー。


スポンサーリンク


スポンサーリンク