[1스4코2파] # 162. LeetCode Pattern 104. Maximum Depth of Binary Tree

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (162차)
[4코1파] 2023.01.13~ (154일차)
[1스4코1파] 2023.04.12~ (65일차)
[1스4코2파] 2023.05.03 ~ (44일차)

Today :

2023.06.13 [162일차]
LeetCode Patterns
104. Maximum Depth of Binary Tree
https://leetcode.com/problems/maximum-depth-of-binary-tree/

104. Maximum Depth of Binary Tree

https://leetcode.com/problems/maximum-depth-of-binary-tree/

문제 설명

binary tree와 target이 주어졌을때, 해당 tree의 max node를 찾는 것! 트리의 depth 찾기

문제 풀이 방법

정점에서 leaf node 까지 움직이면서 depth를 +1 해주고 max 값을 찾는다.
recusrion 사용하는 방법이랑 그냥 stack에 넣는 방법 둘 다 있음

내 코드

(1) recursion

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 dfs(root, depth):
            if not root:
                return depth
            return max(dfs(root.left, depth+1), dfs(root.right, depth+1))
        
        return dfs(root,0)

(2) stack 쓰기

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:
        stack = [[root, 1]]
        cnt = 0
        
        while stack:
            node, depth = stack.pop()
            
            if node:
                cnt = max(cnt, depth)
                stack.append([node.left, depth+1])
                stack.append([node.right, depth+1])
                
        return cnt

증빙

이거 recursion

이거 stack

여담

집 에 가 곱 하