[LeetCode] 117번 문제를 풀어보았다. (ft. java)

2022년 05월 13일 금요일 - 꿀맛같은 금욜!

오늘 올려볼 문제는 117번 Populating Next Right Pointers in Each Node II 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

아뉘 이상한거에서 자꾸 걸려씀

입력

사진에서도 볼 수 있듯이 Binaray Tree의 root가 입력으로 들어온다.

---

풀이 및 코드

같은 레벨에 있는 오른쪽 노드를 next에 바인딩하여 리턴하는 문제다.

오늘은 처음부터 정답을 생각해냈다.

왼쪽부터 탐색하는 bfs로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public Node connect(Node root) {
        if(root == null) return root;

        Queue<Node> q = new LinkedList<>();
        q.add(root);

        while(!q.isEmpty())
        {
            int size = q.size();

            for(int i = 0; i < size; i++)
            {
                Node now = q.poll();

                now.next = i == size - 1 ? null : q.peek();

                if(now.left != null) q.add(now.left);
                if(now.right != null) q.add(now.right);
            }
        }

        return root;
    }
}

---

제출 화면

사실 follow up으로 풀고 싶었는데 너무 어려워서 그냥 O(N) 메모리로 풀었다.

내일은 follow up이 있다면 follow up으로 문제를 풀 수 있었으면 좋겠다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.