문제 요약
자세한 내용은 leetcode에서 확인
https://leetcode.com/problems/maximum-depth-of-binary-tree/
바이너리 트리의 최대 깊이 레벨을 찾아라. root의 깊이는 1이다.
풀이
스택을 사용하는 DFS로 트리를 순회한다. 스택에 노드 대신에 wrapper 클래스를 만들어서 노드와 현재 깊이 레벨을 저장하고 그걸 push 한다.
public int maxDepth(TreeNode root) {
if (root == null) return 0;
// 전형적인 DFS를 위한 스택 생성
Stack<NodeWrapper> s = new Stack<>();
// 항상 root을 가진 상태로 시작. root의 깊이 레벨은 1
s.push(new NodeWrapper(root, 1));
int maxLevel = 0;
while (!s.isEmpty()) {
NodeWrapper w = s.pop();
// 만약 노드가 null이면 스택에 다음 노드로 이동
if (w.node == null) {
continue;
}
// 현재 깊이 레벨과 최대 깊이 레벨 비교
maxLevel = Math.max(maxLevel, w.depth);
// 노드의 자식들을 스택에 넣는다
s.push(new NodeWrapper(w.node.left, w.depth + 1));
s.push(new NodeWrapper(w.node.right, w.depth + 1));
}
return maxLevel;
}
// 노드와 현재 깊이 레벨을 들고있는 클래스
class NodeWrapper {
TreeNode node;
int depth;
public NodeWrapper(TreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}
Complexity
time: O(n) - 노드의 총 갯수인 n 만큼 계산한다.
space: O(1) - 몇개 안되는 변수를 생성하였다.