본문 바로가기

컴퓨터/코테

릿코드 104 - 트리의 가장 깊은 층

# 재귀 버전
class Solution(object):
    def pre(self, node, count, depth):
        count += 1
        if node.right:
            self.pre(node.right, count, depth)
        if node.left:
            self.pre(node.left, count, depth)
        if count > depth[0]:
            depth[0] = count

    def maxDepth(self, root):
        depth = [0]
        if root:
            self.pre(root, 0, depth)
        return depth[0]



# iter 버전
class Solution(object):
    def maxDepth(self, root):
        stack = [(1, root)]
        maxDepth = 0
        while len(stack):
            depth, node = stack.pop()
            if node:
                maxDepth = max(depth, maxDepth)
                stack.append((depth + 1, node.left))
                stack.append((depth + 1, node.right))
        return maxDepth

각각의 장단점이 있다. 재귀버전은 메모리는 좀 잡아먹더라도 실행시간이 빠르고 iter은 실행시간은 재귀에 비해 좀 더 걸리지만 메모리는 O(n) 정도로 굉장히 적게 썼다.

'컴퓨터 > 코테' 카테고리의 다른 글