LeetCode 116. Populating Next Right Pointers in Each Node 자바 문제 풀이

문제

Populating Next Right Pointers in Each Node - LeetCode

문제 해결 방법

• 기본적인 트리가 주어지고, 이를 연결하는 문제입니다.
• level order을 돌며, 각 노드를 연결하는 알고리즘이 필요합니다.
  • 문제에서 perfect binary tree라고 하였습니다., 즉 비어있는 노드는 존재하지 않습니다.
  • level 1일때, level2를 모두 연결합니다.
  • 트리의 가장 왼쪽 노드를 levelStart로 설정합니다.
  • 다음 노드와 연결합니다.(상위 레벨이 이미 연결되있으므로, 이동이 쉽습니다.)
  • 다음 노드의 왼쪽노드가 존재하지 않는다면, 현재 레벨은 모두 연결이 끝난것입니다.
• BFS=level order, 재귀함수를 사용가능합니다.
• 재귀함수는 복잡한 작업을 단순화할 수 있는 경우에 자주 사용하는데, 이 문제는 이전 값을 계산한 값을 필요하지 않고 단순한 level order를 해야 하는 문제이기 떄문에 필요하지 않습니다.
• 오히려 트리가 크다면 stackoverflow가능성이 있으므로, 지양하는게 좋습니다.

Github Link

https://github.com/eunhanlee/LeetCode_116_PopulatingNextRightPointersinEachNode_Solution.git

시간복잡도: O(n), 공간복잡도: O(1)

class Solution {
    /**
     * 주어진 이진 트리의 각 노드에 대해 오른쪽 포인터를 설정하여 연결합니다.
     *
     * @param root 이진 트리의 루트 노드
     * @return 연결된 이진 트리의 루트 노드
     */
    public Node connect(Node root) {
        if (root == null)
            return null;

        // 레벨의 가장 왼쪽 노드
        Node levelStart = root;

        while (levelStart.left != null) {
            // 현재 노드
            Node curr = levelStart;

            while (curr != null) {
                // 현재 노드의 왼쪽 자식의 next 포인터를 오른쪽 자식으로 설정
                curr.left.next = curr.right;
                // 현재 노드의 오른쪽 자식의 next 포인터를 다음 노드의 왼쪽 자식으로 설정
                if (curr.next != null) curr.right.next = curr.next.left;
                // 레벨의 다음 노드로 이동
                curr = curr.next;
            }

            // 다음 레벨의 가장 왼쪽 노드로 이동
            levelStart = levelStart.left;
        }

        return root;
    }
}