[LeetCode] 116. Populating Next Right Pointers in Each Node - 문제풀이

Description

완전이진트리에서 같은 깊이의 오른쪽에 있는 노드를 연결해나가는 문제입니다.

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example 1:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation:Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 212 - 1].
• 1000 <= Node.val <= 1000

Follow-up:

• You may only use constant extra space.
• The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

Solution 1. DFS 재귀 호출1

public ListNode middleNode(ListNode head) {

    if(root == null) { return root;} // edge case
    this.dfs(root.left,root.right); // 전위순회하며 좌표 저장 & left right next로 1차 연결
    return root;
}

private void dfs(Node left, Node right){
    if(left == null || right ==null) return;
    left.next = right;
    dfs(left.left,left.right);
    dfs(left.right,right.left);
    dfs(right.left,right.right);
}

깊이우선탐색을 통해 양쪽 노드를 연결하는 dfs()함수를 재귀호출하여 모든 노드를 탐색하며 next 노드를 연결해 줍니다. left,, right처럼 직접 인접한노드가 아닌 경우에는 현재 노드의 right 노드와 next.left를 연결하는게 포인트입니다.

Solution 2. DFS 재귀 호출2

public ListNode middleNode(ListNode head) {

    if(root == null) return root;
    this.dfs2(root);
    return root;
}

public void dfs2(Node node) {
    if(node == null || node.left == null) return;
    node.left.next = node.right;
    if(node.next != null) node.right.next = node.next.left;
    dfs2(node.left);
    dfs2(node.right);
}

1번 솔루션과 유사하게 양쪽 노드를 연결하는 dfs()함수를 재귀호출하여 모든 노드를 탐색하며 next 노드를 연결해 줍니다. 재귀 호출하는 주체가 노드 자체를 기준으로 하는 것이 다르고 기본적인 컨셉은 동일합니다.

Solution 3. 반복 처리

public ListNode middleNode(ListNode head) {

    if(root == null) return root;
    Node node = root;

    while(node.left != null){  // 2차원배열의 순환 같이 1depth씩 순차적으로 돌면서 처리
        Node prev = node;   // 이전 deapth의 첫번째 노드 기억
        while(node != null){ // 끝까지 와서 next가 null이면 다음 depth로
            node.left.next = node.right;
            if(node.next != null){
                node.right.next = node.next.left;
            }
            node = node.next;
        }
        node = prev.left;
    }
    return root;
}

재귀호출 없이 너비 우선 탐색(BFS)과 유사하게 Depth별로 순차적으로 돌면서 동일 Depth의 모든 요소의 next를 처리했을때 다음 Depth로 내려가 처리하는 방식입니다. 2차원 배열을 순회하는 로직과도 유사하게 생각하시면 편할 것 같습니다.

Reference

Populating Next Right Pointers in Each Node - LeetCode