みんな大好きLeetCodeの時間です
今回は117. Populating Next Right Pointers in Each Node II です
次の右ノードを指すように，各 next ポインタを生成
次の右ノードが存在しない場合，次のポインタはNULLに設定
初期状態では，すべての次のポインタはNULLに設定されている
とのことです。
Follow Upでは次のように記載されています。
一定の余分なスペースのみ利用可能
再帰的なアプローチが望ましい、暗黙のスタックスペースは余分なスペースとしてカウントされない
アプローチ
最初の階層である１の次のポインターは常にNullを指しています。
・次の階層ではダミーノードを設定します。
・１に対して左のNodeが存在したらtempを２に更新します。
・さらに１に対して右のNodeがいたらtempを3にします。
・3の次のNodeはデフォルトで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 46 47 48 49 50 51 |
/* // 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) { if(root == null) return null; Node head = root; while(head != null){ Node temp = new Node(0); //次の階層に移るために保持しておく Node dummy = temp; while(head != null){ if(head.left != null){ temp.next = head.left; temp = temp.next; } if(head.right != null){ temp.next = head.right; temp = temp.next; } //左のNodeの場合は右のNodeへ、右のNodeだとNullなので次の階層へ head = head.next; } //次の階層に移動する head = dummy.next; } return root; } } |
というわけで今回はここまで！
