[LeetCode][Python3] 104. Maximum Depth of Binary Tree

# 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: TreeNode) -> int:
        def nowDepth(node,depth):
            if(node==None):
                return depth
            else:
                if(nowDepth(node.left,depth+1)>=nowDepth(node.right,depth+1)):
                    return nowDepth(node.left,depth+1)
                else:
                    return nowDepth(node.right,depth+1)
        return nowDepth(root,0)

recursive하게 코드를 짰더니 매우 깊은 Tree에서는 Time Limit 에 걸렸다.

 

따라서 iterative하게 짜야한다.

# 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: TreeNode) -> int:
        if not root : return 0
        queue=[]
        queue.append(root)
        depth = 0
        while(len(queue)!=0):
            depth+=1
            for _ in range(0,len(queue)):
                node = queue.pop(0)
                if node.left!=None:
                    queue.append(node.left)
                if node.right!=None:
                    queue.append(node.right)
        return depth
        

bfs를 사용하였다.

 

-추가-

 

그런데 다른 분들의 코드와 비교해보니 코드 구성이 유사한데 time limit이 걸려 더 큰 값을 비교하는 if else문을 max를 사용하여 바꿨더니 성공했다.

그 뿐만 아니라 매우 빠르다.

Runtime: 28 ms, faster than 99.60% of Python3 online submissions for Maximum Depth of Binary Tree.
Memory Usage: 16.4 MB, less than 12.67% of Python3 online submissions for Maximum Depth of Binary Tree.

# 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: TreeNode) -> int:
        def nowDepth(node,depth):
            if(node==None):
                return depth
            else:
                return max(nowDepth(node.left,depth+1),nowDepth(node.right,depth+1))
        return nowDepth(root,0)

function call로 발생하는 시간 때문에 time limit이 난게 아니라 branch( if else)로 발생하는 시간 때문이었던것 같다.

 

max 함수가 어떤 식으로 작동하는 지 알아보고 싶다. -> 조건문으로 만들어진 함수가 아닐테니까.