[Java][트리] Leetcode - 116. Populating Next Right Pointers in Each Node

Populating Next Right Pointers in Each Node - LeetCode

Populating Next Right Pointers in Each Node - LeetCode

완전 이진트리를 가지고 푸는 문제로, 재귀 없이 BFS적으로 접근하면서 풀 수 있다. 문제의 번역은 아래와 같다.

완전 이진 트리는 리프(끝 노드)가 모두 같은 레벨에 있고, 모든 부모 노드는 두 개의 자식 노드를 가진다. 한 마디로, 모든 레벨이 꽉꽉 차있는 트리를 의미한다. 노드의 구조는 아래와 같다.

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

각 노드의 next에 같은 레벨에서 우측에 있는, 즉 우측으로 다음에 있는 것을 채워넣어 루트를 반환하라. 우측 노드가 없는 경우, null 을 채우면 된다. 모든 next 포인터들은 null 로 초기화 된 상태이다.

Example 1:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
레벨의 끝마다 #이 붙는다고 생각하면 된다.

Constraints:

• 노드의 개수는 4096개 이하이다.
• -1000 <= node.val <= 1000

답

트리 문제의 경우, 많은 케이스가 재귀로 접근해야 하는 것이 많아서 고민을 좀 했으나, 완전 이진 트리라는 제한을 잘 살려서 레벨마다 연결을 해주면서 내려가면 되겠다는 생각이 들었다.

우선 모든 노드의 왼쪽 자식의 next 를 오른쪽 자식으로 해줘야 하고, 고민이 들었던 부분은 위의 그림 기준으로 5와 6을 연결하는 방법이었다.

여기서 발상은, 5와 6을 이으려면 2와 3이 연결되어 있으면 root가 2라는 가정 하에, 2의 오른쪽 자식과 2의 next의 왼쪽 자식을 연결하는 것이었다. 다음 레벨을 보는 시점에서 이미 위쪽 레벨은 모두 연결이 되어 있기 때문에, 마치 연결 리스트처럼 위쪽 레벨을 이동하면서 각각의 노드마다 자식들끼리 연결해주고 자신의 오른쪽 자식과 다음 노드의 왼쪽 자식을 연결하면 된다. 유일한 예외를 걸어줄 부분은 해당 레벨의 마지막 노드에 접근했을 땐, 다음 노드의 자식이 아니라 null 과 연결시키면 된다는 점이다.

이렇게 이동하는 기준은 부모 노드지만, 연결 작업은 자식 노드에 실행하게 되는 셈이다. 그래서 root를 부모 노드로 두고, 자식 노드를 이동하기 위한 변수 cur을 두고 이터레이션만으로 정답을 찾을 수 있는 코드를 아래와 같이 작성해보았다.

public class Solution {
    public Node connect(Node root) {
      // 반환을 위한 초기 루트
      Node original_root = root;
      // 시작 노드가 null 이거나 그 자식이 없는 경우 바로 반환
      if (root == null || root.left == null)
        return root;
      // cur = 연결 작업을 하는 레벨의 가장 좌측 노드
      Node cur = root.left;
 
      // root = 연결 작업을 하는 레벨보다 하나 위 레벨의 부모 노드. 
      // root 를 우측으로 이동하면서 연결하고 끝을 만나면 다음 레벨의 가장 좌측 노드로 변경한다.
      // cur는 root가 내려왔으니 마찬가지로 한 레벨 내려간다. 
      while (cur != null) {
        while (root != null) {
          if (root.next == null) { // 해당 레벨 가장 마지막 노드라면
            root.left.next = root.right;
            root.right.next = null;
            break;
          }
          root.left.next = root.right;
          root.right.next = root.next.left;
          root = root.next;
        }
        root = cur;
        cur = cur.left;
      }
      return original_root;
   }
}

한계점

이 접근은 어디까지나 주어진 트리가 완전이진트리이기 때문이라고 본다. 그렇지 않는 트리에서 위의 작업을 해야하는 경우에는 접근을 달리할 필요가 있어 보인다.