문제 링크

나의 논리

트리의 최대 깊이를 찾는 문제이다. 따라서 어찌됬건 트리의 루트부터 트리의 리프노드까지 순회해야된다고 생각했고, 트리의 순회라면 전위순회,중위순회, 후위순회가 있다. 이 각각의 순회의 아이디어는 재귀이며 ,재귀로 아이디어를 구현 할 때에는 그저 재귀함수를 놓는 위치만 달라진다. 이 문제에서는 어느순서로 순회를 하던지 상관없으므로 아무순회방식이나 사용하여도 된다.

순회를 한 후 왼쪽 또는 오른쪽 간선에서 리턴하는 노드의 깊이를 max 함수와 비교 한 후 다음 순회를 하여서

순회를 하면서 가장 큰 노드의 깊이를 유지하다가 최종적으로 리턴한다.

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        
        def traverse(node, num):
            
            if not node.left  and not node.right:
                return num
            
            ret = num
            if node.right:
                ret = max(ret, traverse(node.right,num+1))
            if node.left:
                ret = max(ret,traverse(node.left, num+1))
                          
            return ret
                          
                          
        return traverse(root, 1) if root != None else 0

책의 논리

책에서는 BFS로 풀었다.

루트노드에서 연결된 자식노드를 차례로 탐색하며 부모노드를 방문 할 때마다 깊이는 증가한다.

    def maxDepth(self, root: TreeNode) -> int:
        
        if not root:
            return 0
        
        queue = collections.deque([root])
        depth = 0
        
        while queue:
            depth += 1
            
            for _ in range(len(queue)):
                
                cur = queue.popleft()
                if cur.right:
                    queue.append(cur.right)
                if cur.left:
                    queue.append(cur.left)
                    
        return depth