[이진트리/DFS] Leet code 104 - Maximum Depth of Binary Tree

 

 

1. 스택 활용하는 방법

# 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 root is not None:
            s = [(root, 1)]
        else:
            s = []
        maxValue = 0
        
        while s:
            cur, cnt = s.pop()
            if cur.left is None and cur.right is None:
                if cnt > maxValue:
                    maxValue = cnt
                continue

            if cur.left is not None:
                s.append((cur.left, cnt+1))

            if cur.right is not None:
                s.append((cur.right, cnt+1))

        return maxValue

 

2. 재귀 활용하는 방법

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:

    def __init__(self):
        self.maxValue = 0

    def maxDepth(self, root: TreeNode) -> int:

        if root is not None:
            self.__dfs1(root, 1)
        return self.maxValue

    def __dfs1(self, cur, cnt):

        if cur.left is None and cur.right is None:  # 끝점
            if cnt > self.maxValue:
                self.maxValue = cnt
            return

        if cur.left is not None:
            self.__dfs1(cur.left, cnt + 1)
        if cur.right is not None:
            self.__dfs1(cur.right, cnt + 1)


node = TreeNode(3,TreeNode(9),TreeNode(20,TreeNode(15),TreeNode(7)))
s = Solution()
print(s.maxDepth(node))