Leet code 104 - Maximum Depth of Binary Tree

---

 

첫번째 트리 문제이다.. 처음에는 input이 리스트로 주어지는 줄 알고, 리스트에 null까지 있겠다그냥 단순히 원소 갯수 몇개인지 재귀적으로 나눠주고 +1을 하려햇으나 문제를 잘읽어보면 제일 binary tree node클래스에 대해 정의가 되어 있다.

 

 

 

1. dfs를 이용한 풀이

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:

        '''
        널도 값으로 가지고 있으니까
        결국 원소의 개수가중요하지 않을까?
        2로나눠지는 몫 + 1
        '''
        if root is None: 
            return 0 
        else: 
            left_height = self.maxDepth(root.left) 
            right_height = self.maxDepth(root.right) 
            return max(left_height, right_height) + 1
        print(root)
        print(root.right)
        # return len(root) // 2 + 1

root가 none 이라면 0을 반환, 아닌 경우에는 left, right 에 대해 재귀적으로 ,최대 값을 구한다.

---

2.dfs 를 활용한 풀이

 

deque 자료형을 임포트 해 사용한다.

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

from collections import deque

class Solution:
    def maxDepth(self, root):
        if root is None:
            return 0

        queue = deque([(root, 1)])
        while queue:
            node, level = queue.popleft()
            if node.left:
                queue.append((node.left, level + 1))
            if node.right:
                queue.append((node.right, level + 1))

        return leve

deque 에는 첫번째 루트와 레벨 1 이들 어간다. 여기서 데크는 스케줄링공간으로 쓰인다.

이후 팝되고 레프트와 라이트에 대한 정보를 level +1 해서 함께 데크에 넣는다.

이러면 낮은 레벨부터 순차적으로 탐색하는 dfs 알고리즘이 만들어진다.