[LeetCodeやるお]117. Populating Next Right Pointers in Each Node II

みんな大好きLeetCodeの時間です
今回は117. Populating Next Right Pointers in Each Node II です

次の右ノードを指すように，各 next ポインタを生成
次の右ノードが存在しない場合，次のポインタはNULLに設定
初期状態では，すべての次のポインタはNULLに設定されている

とのことです。

Follow Upでは次のように記載されています。

一定の余分なスペースのみ利用可能
再帰的なアプローチが望ましい、暗黙のスタックスペースは余分なスペースとしてカウントされない

アプローチ

最初の階層である１の次のポインターは常にNullを指しています。

・次の階層ではダミーノードを設定します。
・１に対して左のNodeが存在したらtempを２に更新します。
・さらに１に対して右のNodeがいたらtempを3にします。
・3の次のNodeはデフォルトでnullなのでここで処理をやめます。

次の階層のノードに移り、同様に繰り返していきます。

スポンサーリンク

実装

/*
// 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;
        
    }
}

というわけで今回はここまで！