LeetCode 116(Populating Next Right Pointers in Each Node, java)

0. 문제

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

Populating Next Right Pointers in Each Node - LeetCode

 

 

1. 문제 설명

- 문제에서 완전 이진트리(root)가 주어진다.

- 모든 노드는 next 속성이 있는데, 이는 우측 노드를 가리키는 포인터 역할을 한다.

- 모든 노드의 next 값은 null 값으로 초기화되어있다.

- next 값이 우측에 존재하는 형제 노드를 가리키도록 설정하는 것이 문제의 핵심이다.  

 

 

2. 문제 해설

a) 첫 번째 접근

- 우선 Level order 탐색을 이용한 방법을 생각할 수 있다. 

- 어떤 노드를 방문할 때마다 해당 노드의 좌우에 존재하는 자식 노드를 Queue에 저장한다.

- 그리고 Queue에 저장된 노드를 순서대로 방문한다. 이 과정을 반복한다.

- 그러나 이 방식은 반복문을 이중으로 사용해야 하므로 효율적인 탐색이라고 할 수는 없다.

 

 

b) 두 번째 접근 

- 더욱 효율적인 탐색을 위해 재귀 함수를 사용할 수 있다. 

- 완전 이진트리는 좌측 자식 노드가 존재하는 경우, 우측 노드는 무조건 구조적 특징을 가진다.

- 이 특성을 이용하여 재귀적으로 탐색을 수행할 수 있다. 

 

- 다음 코드를 보면서 이해해보자. 

 

 

3. 정답 코드

a) Queue를 사용한 방법

class Solution {
    public Node connect(Node root) {
        
        if(root == null) return null; 
        Queue<Node> que = new LinkedList<>();
        que.offer(root);
        
        while(que.size() > 0) {
            int count = que.size();
            while(count > 0) {
                count--;
                Node node = que.poll();
                
                if(count > 0) {node.next = que.peek();}
                else if(count == 0) {node.next = null;}
       
                if(node.left != null) {que.offer(node.left);}
                if(node.right != null) {que.offer(node.right);}
            }
        }
        return root;
    }
}

 

 

b) 재귀를 사용한 방식 

class Solution {
    public Node connect(Node root) {
        
        if(root == null) return null;
        
        if(root.left != null) {
            root.left.next = root.right;
        }
        
        if(root.right != null && root.next != null) {
            root.right.next = root.next.left;
        }
        
        connect(root.left);
        connect(root.right);
        return root;
    }
}