[leetcode] 104. Maximum Depth of Binary Tree 파이썬 코드

트리의 최대 높이 구하는 문제이다.

root에서 자식 노드까지 쭉 이어지는 노드를 카운트해서 가장 큰 것이 트리의 최대 높이가 된다.

 

첫 번째 방법: DFS (recursion)

maximum height = 1 + max(dfs(왼쪽 서브트리) + dfs(오른쪽 서브트리))

 

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        if not root: # root is null -> return
            return 0 
        
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

 

재귀를 쓰지 않고도 풀어볼까?

 

두 번째 방법, BFS

- level order traversal

class Solution(object):
    def maxDepth(self, root):

        level = 0
        if root is not None:
            queue = []

            queue.append([root, 1])

            while queue:
                node, level = queue.pop(0)
                if node.left is not None:
                    queue.append([node.left, level + 1])
                if node.right is not None:
                    queue.append([node.right, level + 1])
            
        return level

 

my code

 

class Solution(object):
    def maxDepth(self, root):
    
        if not root:
            return 0

        level = 0
        q = deque([root])
        while q:
            for i in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

            level += 1

        return level

neetcode

 

세 번째 방법, iterative DFS

preorder dfs를 스택을 이용해서 코드를 짜면 된다.

 

class Solution(object):
    def maxDepth(self, root):
        stack = [[root, 1]]
        res = 0

        while stack:
            node, depth = stack.pop()

            if node: # node is not null
                res = max(res, depth)
                stack.append([node.left, depth + 1])
                stack.append([node.right, depth + 1])

        return res

 

 

참고

https://www.youtube.com/watch?v=hTM3phVI6YQ&t=254s