LeetCode/Maximum Depth of Binary Tree

( 블로그 기사 의 전재)

[ h tps : // / ㅇ t 여기. 이 m / p 로 b ぇ ms / 마무 m-에서 pth-o-bi-na ry-t ree / ]

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

return its depth = 3.

다시 바이너리 트리를 다룬 문제로, 가장 계층이 깊은 곳의 나무의 깊이를 돌려줍니다.
개인적으로는 Note에 'Find one line solution.'라고 덧붙여 보고 싶다. 어렵지 않은 문제입니다만, one line으로 쓸 수 있으면 도야 얼굴 결정하고 싶어지네요.

해답·해설

해법 1

One line solution입니다. 스스로 생각하면 기분 좋네요.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right)) if root else 0

"만약 나무가 존재하면 1+(좌우의 나무 중, 보다 깊은 나무의 깊이)를 돌려주어, 나무가 존재하지 않으면 0을 돌려준다"함수를 정의해, recursive를 취해 하면 완성 입니다.

해법 2

물론 Iterative적인 해법도 있습니다. 가독성은 떨어지지만 복잡하지는 않으며 계산 시간도 해법 1에 뒤떨어지지 않습니다.

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        depth = 0
        l = [root] if root else []
        while l:
            depth += 1
            l_tmp =[]
            for t in l:
                if t.left:
                    l_tmp.append(t.left)
                if t.right:
                    l_tmp.append(t.right)
            l = l_tmp

        return depth

deque형을 사용해도 쓸 수 있습니다만, 이번은 요소를 꺼내는 조작은 없고 루프를 돌리는 것만이므로, deque형을 일부러 사용하는 메리트는 없습니다.