[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（繰り返し）で解いていきます。

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

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