재귀함수: 리턴 값

문제:
트리의 가장 깊은 깊이 출력

평소 풀던 방식: 재귀함수가 base condition 만족할 때마다 global변수 갱신.

def maxDepth(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node, n):
            nonlocal ans
            if node is None:
                ans = max(ans, n)
                return
            dfs(node.left, n+1)
            dfs(node.right, n+1)
        
        dfs(root, 0)
        return ans

이 방식은 나중에 memoization, dp할 때 응용이 힘들다.

재귀함수 자체가 리턴값을 같게 한다:

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def dfs(node, depth):
            if not node:
                return depth
            return max(dfs(node.left, depth+1), dfs(node.right, depth+1))
        
        return dfs(root, 0)

이 방식을 연습,,

좋은 웹페이지 즐겨찾기