104. Maximum Depth of Binary Tree

    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        if (root.left == null && root.right == null) return 1;

        if (root.left != null && root.right == null) return maxDepth(root.left) + 1;
        if (root.left == null && root.right != null) return maxDepth(root.right) + 1;

        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

풀이 방법은 여러 가지가 있겠다. 

BFS, 재귀...

 

먼저 BFS로 푼 것이다. 

Queue에 넣고 해당 길이만큼 돌면서 자식 추가하고, 반복하기

 

for문 안에서 append를 하면 len에 영향을 주는 것으로 생각했지만, 이미 len을 결정된 뒤여서 영향을 받지 않는것 같다.

 

자바로 푼 재귀 버전

풀이 시기를 보니, 지금으로부터 5년전에 풀었던거였다.

    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        queue = collections.deque([root])
        depth = 0

        while queue:
            depth += 1
            #print(f'depth = {depth}, len(queue) = {len(queue)}')
            for _ in range(len(queue)):
                cur_root = queue.popleft()
                if cur_root.left:
                    queue.append(cur_root.left)
                if cur_root.right:
                    queue.append(cur_root.right)
        return depth