(Leetcode) 102 - Binary Tree Level Order Traversal
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
https://leetcode.com/problems/binary-tree-level-order-traversal/
내가 작성한 풀이
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
dfs(result, root, 0);
return result;
}
public void dfs(List<List<Integer>> result, TreeNode node, int level) {
if(node == null) {
return;
}
if (result.size() <= level) {
result.add(new ArrayList<>());
}
result.get(level).add(node.val);
dfs(result, node.left, level + 1);
dfs(result, node.right, level + 1);
}
}
TC, SC
시간 복잡도는 O(n)이고, 공간 복잡도는 O(n)이다. 트리가 균등한 형태일 경우 공간 복잡도는 O(logn)에 가까워진다. (결과에 사용되는 list는 고려하지 않는다.)