[LeetCode] 116. Populating Next Right Pointers in Each Node - BFS...

[LeetCode] 116. Populating Next Right Pointers in Each Node - BFS...

728x90

문제

완벽 이진 트리(Perfect Binay tree)의 노드들이

같은 레벨의 오른쪽 노드의 포인터를 가질 수 있게 하라

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

문제 해결 방안

한 레벨별로 생각을 한다.

각 레벨을 Queue에 넣게 되면, Queue의 오른쪽 아이템은 내 오른쪽 노드가 된다.

레벨 3이 Queue에 있다면, [4, 5, 6, 7]과 같이 된다.

그렇다면 queue[0]의 right는 queue[1]이 되는 식이다.

주의할 점

일반 BFS와 같이 진행을 하게 되면 3의 오른쪽 노드가 null이 아니라 4가 된다.

왜냐하면 Queue: [2, 3]상태였다가 2의 자식 4, 5를 추가하면서

Queue: [3, 4, 5]와 같이 되기 때문이다.

그렇기 때문에 각 레벨단위로 끊어서 계산을 해 줄 것이다.

코드 (TypeScript)

function connect(root: Node | null): Node | null { let queue = [root]; // length: node count of current level let length = queue.length; while (length > 0) { for (let i = 0; i < length; i++) { let node = queue.shift(); if (node === null) { continue; } // last item's right is null. let next = i === length - 1 ? null : queue[0]; node.next = next; // insert left and right queue.push(node.left); queue.push(node.right); } // reset length of this level length = queue.length; } return root; };

728x90

from http://goldfishdiary.tistory.com/93 by ccl(A) rewrite - 2021-11-02 14:25:55