728x90

Q. 입력 받은 Tree의 root를 이용해 Tree 각 층의 Node 너비(=개수)를 알아내는 function 작성하라.

--- Example
Given:
0
  / |  \ 
1   2   3
|       |
4       5

Answer: [1, 3, 2]

🎈 Tree traverseBF(BFS) method와 비슷하다.
배열을 선언해 초기 값으로 root와 각 층의 끝을 알려주는 문자('s')를 넣어주고, 이런 형식으로 반복 해주면 된다.
또한, 이 과정에서 각 층의 Node를 count해줘야 한다.

Tree Level Width Algorithm의 이미지화

🧨 위의 이미지를 보며 어떻게 풀어나갈 지 생각해보자

1. []의 초기값 선언
2. while 조건문은 어떻게?
3. while 내부에서 's'처리는 어떻게?
4. count 방식은 어떻게?

위 4가지만 잘 생각해주면 문제는 생각보다 쉽게 해결된다.

Tree Level Width Algorithm 정답 코드

🔮 arr 배열에 [ root, 's' ]를 넣어주고 시작해야 한다. while 조건문으로 arr.length > 1을 줄 것이기 때문이다.
위와 같이 조건문을 작성하면, 마지막 's'가 남았을 때 while을 끝낼 수 있다.
여기서 counters 배열에 0을 넣고 시작하는 것도 중요한 팁이다.
보통 counter를 한다고 생각하면, count변수를 따로 만들어 count++를하고 반환할 결과 배열에 push(count)할 것이다.
하지만, 방금 작성한 방법을 사용하면 위의 while에서는 마지막 count를 결과 배열에 push하지 못한다.

전 글의 Tree traverseBF(orDF) method에서 했던 것처럼, arr.shift()을 해서 가장 첫 번째 index 값을 가져온다.
만약 's'면, 해당 width count는 끝났으며, 다음 level의 children이 모두 arr에 push된 것이므로,
새로운 counters를 push해줌과 동시에 해당 width의 끝을 알리는 's'도 push해준다.
's'가 아니라면, 위와 반대로 해당 level을 count하고 있으며, 다음 level의 children을 push하고 있는 것이므로
arr.pushcounters++를 진행해준다.

Full Code

function levelWidth(root) {
const arr = [root, 's'];
const counters = [0];
 
while (arr.length > 1) {
const node = arr.shift();
 
if (node === 's') {
counters.push(0);
arr.push('s');
} else {
arr.push(...node.children);
counters[counters.length - 1]++;
}
}
 
return counters;
}

+ Recent posts