[Binary Tree - DFS, Easy] Maximum Depth of Binary Tree

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75

간단한 DFS 문제다.
재귀로 풀기 위해 메서드를 따로 뺐고, depth 누계를 가지고 다니도록 했다.

탈출조건은 node == null로 했고, 탐색은 node.left 선행 후 node.right 수행되도록 했다.

모든 재귀가 종료되고 첫 호출된 dfs 메서드로 돌아왔을 때, left와 right값 중 더 높은 값을 리턴하면 된다.

class Solution {
    public int maxDepth(TreeNode root) {
        return dfs(root, 0);
    }

    public int dfs(TreeNode node, int depth) {
        if (node == null) {
            return depth;
        }

        int left = dfs(node.left, depth + 1);
        int right = dfs(node.right, depth + 1);

        return Math.max(left, right);
    }
}

하는 김에 스택으로도 풀어봄
Depth를 체크하기 위해 별도의 stack생성, push시 마다 +1로 같이 넣어준다.

class Solution {
    public int maxDepth(TreeNode root) {
        int max = Integer.MIN_VALUE;

        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> depthStack = new Stack<>();
        stack.push(root);
        depthStack.push(1);

        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();
            int currentDepth = depthStack.pop();

            if (current.left == null && current.right == null) {
                max = Math.max(max, currentDepth);
                continue;
            }

            if (current.left != null) {
                stack.push(current.left);
                depthStack.push(currentDepth + 1);
            }
            if (current.right != null) {
                stack.push(current.right);
                depthStack.push(currentDepth + 1);
            }
        }
        return max;
    }
}

솔루션 참고해보면 재귀로 푸는 방법중에 아래와 같이 해도 된다.
내가 푼게 루트부터 리프까지 누계하는 방법이라면
이것은 리프부터 루트까지 누계하는 방법이라고 볼 수 있다.

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}