Binary Tree Level Order Traversal II
문제 설명
Binary Tree가 인자로 주어지고 tree를 순회하며 가장 마지막 노드부터 단계적으로 배열에 값을 저장하는 것이다.
문제 예시
[input]
3
/ \
9 20
/ \
15 7[output]
[
[15, 7],
[9, 20],
[3],
]풀이 1 - BFS (non-recursive)
var levelOrderBottom = function(root) {
if (!root) return []
const arr = [root];
const result = [];
while (arr.length) {
const size = arr.length;
const values = []
for (let i = 0; i < size; i++) {
const node = arr.shift()
values.push(node.val)
if (node.left) arr.push(node.left)
if (node.right) arr.push(node.right)
}
result.unshift(values)
}
return result
};풀이2 - BFS (Recursive)
var levelOrderBottom = function(root) {
var output = [];
bfs(root, 0, output)
return output.reverse();
};
var bfs = function(node, level, output) {
if (!node) return;
if (!output[level]) output[level] = [];
output[level].push(node.val);
bfs(node.left, level + 1, output);
bfs(node.right, level + 1, output);
}핵심부분
예전에 알고리즘을 풀때는 BFS를 정확하게 이해하지 못했다. 숙련도가 조금씩 늘어나면서 Tree의 BFS 풀이법을 보면서 Queue를 활용해야 한다는 점, 그리고 어떻게 순회해야하는지에 대해 이해하고 개념이 쌓여가는 것 같다. 물론 아직 문제조차 풀지 못했지만, 계속 풀면서 키포인트를 찾는 연습이 필요하다고 생각한다.
도움받은 문서
공부한 내용을 정리하는 공간으로 학습 중 습득한 내용이 정확하지 않은 정보를 포함할 수 있어 추후 발견시 수정하도록 하겠습니다.