Maximum Depth of Binary Tree

박수빈·2022년 1월 20일
0

leetcode

목록 보기
7/51
post-custom-banner


문제

  • 트리가 주어졌을 때, root 부터 가장 깊은 depth 구하기

풀이

recursion으로 가장 leaf에 도달했을 때, 값 저장하기

# 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:
        global maxDepth
        if root:
            maxDepth = 1
            solution(root, 1)
            return maxDepth
        else:
            return 0
        
        
        
def solution(thisNode, depth):
    global maxDepth
    if thisNode.left is None and thisNode.right is None:
        maxDepth = max(maxDepth, depth)
        return
    if thisNode.left:
        solution(thisNode.left, depth+1)
    if thisNode.right:
        solution(thisNode.right, depth+1)

결과


느리지만 성공...!
stack으로 dfs하면 좀 더 빠르려나... 하지만 넘 ㅜ귀찮은걸

profile
개발자가 되고 싶은 학부생의 꼼지락 기록
post-custom-banner

0개의 댓글