LeetCode: Maximum Depth Of Binary Tree

오늘부터 LeetCode 12월간 챌린지가 시작했다.
31일동안 꾸준히 풀어봐야지!
오늘의 문제는 tree에 관한 문제였다.

문제풀이

트리에서 가장 높은 높이가 몇인지 찾는 문제였고, 트리의 순회가 생각 나는 문제였다.
이전에 풀었었던 트리 순회 문제들은 Array로 input을 받아서 순회 방문 여부를 나타내는 boolean 변수로 방문 여부를 확인했었다.

이 문제에서는 input이 node로 표현된 tree이다.
나는 중위순회로 tree를 순회했다.
root를 stack에 넣은채로 시작했고, 시작 height는 1로 했다.

stack이 empty가 되기 전까지 순회를 했다.
leaf 노드는 left, right가 모두 null이라는 특성을 이용해서 만약 stack의 최상단 node의 left, right가 모두 null이면 leaf 노드로 판단했다.
leaf 노드라면 stack에서 pop하고 트리에서 위쪽으로 올라간 뒤 다시 탐색을 해야하므로 height를 감소시켰다.

현재 노드에서 자식 노드가 있다면 height를 증가시키고, 현재 최대값과 height를 비교해서 최대값을 저장했다.
트리의 중복 순회를 방지하기 위해 stack에 넣기 전 이전의 스택과 자식 노드간의 링크를 끊는 작업을 진행했다.

import java.util.*;
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int answer = 1;
        int height = 1;
        Stack<TreeNode> s = new Stack<>();
        s.add(root);
        while(!s.isEmpty()) {
            if(s.peek().left == null && s.peek().right == null) {
                height--;
                s.pop();
                continue;
            }
            if(s.peek().left != null) {
                height++;
                answer = Math.max(answer, height);
                TreeNode temp = s.peek().left;
                s.peek().left = null;
                s.add(temp);
                continue;
            }
            if(s.peek().right != null) {
                height++;
                answer = Math.max(answer, height);
                TreeNode temp = s.peek().right;
                s.peek().right = null;
                s.add(temp);
                continue;
            }
        }
        return answer;
    }
}