117. Populating Next Right Pointers in Each Node II

문제

Left, Right, Next 포인터를 가진 노드가 주어지면,

왼쪽에 있는 노드가 자신의 오른쪽 노드를 가리키도록 추가하는 문제입니다.

해당 문제는 완벽한 이진트리가 아니기 때문에 오른쪽 노드가 없다면, 그 다음 오른쪽 노드를 가리켜야 합니다.

 

 

위 그림의 5번 원소의 오른쪽은 비어있습니다. 하지만, 그 다음 오른쪽에 7 원소가 있기 때문에 7을 Next 포인터로 가리키면 됩니다.

 

문제 풀이

중첩 반복문을 이용한 풀이입니다.

반복문이 아닌 dfs 재귀로 풀 수 있는 방법도 있습니다.

 

public Node connect(Node root) {
    Node node = root;

    while (node != null) {
        Node dummy = new Node(); 
        Node needle = dummy;

        while(node != null) {
            if(node.left != null) {
                needle.next = node.left;
                needle = needle.next;
            }

            if(node.right != null) {
                needle.next = node.right;
                needle = needle.next;
            }

            node = node.next;
        }

        node = dummy.next;
    }

    return root;
}

 

1. 루트 노드 기준으로 왼쪽 자식 노드가 존재하면,

needle.next 에 node.left 를 가리키도록 합니다. (그 윗줄에서 needle 은 dummy 를 가리키고 있으니 실제로는 dummy 의 next 도 node.left 를 보게 됩니다.)

 

위 예시 그림으로 보자면, dummy.next 와 needle 은 2원소를 보고 있는 상태입니다. 

 

2. 루트 노드 기준으로 오른쪽 자식 노드가 존재하면,

needle.next 에 node.right 값을 가리킵니다.

 

위 1번에서 needle 은 2원소이기 때문에 needle.next = node.right 코드 동작은 2원소의 next 가 3을 가리키게 됩니다.

 

3. node = node.next 코드는 현재 루트노드는 next 원소가 없기 때문에 null 이 됩니다.

 

4. node = dummy.next 코드는 특정 계층 (1계층, 2계층 등 특정 계층이 끝났을 때 다음 계층의 node 를 실행하기 위한 코드입니다.)

 

첫번째 1~3번 로직이 완료되면 이제 2번째 계층의 시작인 2원소가 node 가됩니다.

2원소 기준으로 위 1번~3번을 똑같이 실행합니다.

 

그런데 4 원소가 5 원소를 가리키게 되고, 5 원소는 다음 원소를 가리켜야하는데 바로 오른쪽 원소가 없습니다.

이때 3번째 로직(node = node.next) 에 의해 현재 node 는 2 가 아닌 3이 되어있기 때문에 5원소가 7 원소를 가리킬 수 있게됩니다. 

 

 

재귀를 이용한 풀이입니다.

public Node connect(Node root) {
    recurse(root);
    return root;
}

private void recurse(Node root) {
    if(root == null) return;

    Node dummy = new Node();
    Node needle = dummy;

    while(root != null) {
        if(root.left != null) {
            needle.next = root.left;
            needle = needle.next;
        }
        if(root.right != null) {
            needle.next = root.right;
            needle = needle.next;
        }

        root = root.next;
    }

    recurse(dummy.next);
}

 

기존 반복문 코드와 거의 동일하지만, 다음 계층(level) 원소를 순회할때 재귀함수로 동작하기 위한 recurse(dummy.next) 부분만 다릅니다.