参照：https://leetcode.com/problems/populating-next-right-pointers-in-each-node/solution/
完全二分木があって、次の右ノードを指すように，各 next ポインタを生成する。
次の右ノードがない場合，次のポインタはNULLに設定される
初期状態では、すべての次のポインタはNULLに設定されています。
アプローチ
アプローチとして、これをIteratevely（繰り返し）で解いていきます。
・まずは各層で初期化するポインターを作ります。
・同じ階層の中で全ての子ノードに対してnextを修正していきます。
・各階層で一番右のノードはそれ以上右のノードを持たないのでNullをセットします。
・一つの階層で処理が終わったら下のレベルに移ります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
/* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; } }; */ class Solution { public Node connect(Node root) { Node leftNode = root; while(leftNode != null && leftNode.left != null){ populateLeftNode(leftNode); leftNode = leftNode.left; } return root; } private void populateLeftNode(Node startNode){ Node iter = startNode; while(iter != null){ iter.left.next = iter.right; if(iter.next != null){ iter.right.next = iter.next.left; } iter = iter.next; } } } |
スポンサーリンク
解説
まずはポインターを作成します
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の時、４の次のポインターは５になります。
iterがnullでない＝右端でない場合、
if(iter.next != null){
iter.right.next = iter.next.left;
iterが2の時、5の次のポインターは2の次の左、なので6になります。
ポインターを２の次に移します。
iter = iter.next;
と、まぁこんな感じ。つれー。
