99클럽 코테 스터디 33일차 TIL + 리트코드 깊이너비탐색

 

오늘의 주제 : 깊이 너비 탐색문제

링크 : https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/?envType=daily-question&envId=2024-07-18

 

# 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 countPairs(self, root: TreeNode, distance: int) -> int:
        self.result = 0
        
        def dfs(node):
            if not node:
                return []
            # 리프 노드를 찾으면 [1] 반환 (자기 자신까지의 거리 1)
            if not node.left and not node.right:
                return [1]
            
            # 왼쪽과 오른쪽에서 리프 노드까지의 거리를 계산
            left_distances = dfs(node.left)
            right_distances = dfs(node.right)
            
            # 좋은 쌍을 계산
            for ld in left_distances:
                for rd in right_distances:
                    if ld + rd <= distance:
                        self.result += 1
            
            # 각 리프 노드까지의 거리를 1씩 증가시켜 반환
            return [d + 1 for d in left_distances + right_distances]
        
        dfs(root)
        return self.result

 

- 오늘의 회고록

일단 혼자 스택/큐에 대해 공부하고있는데

dfs가 자꾸 나오는거보니 중요하긴 한가보다....

스택/큐한다음엔 dfs, bfs 공부를 해야겠다고 생각했다

 

이제 근데 그건앎

이걸 dfs로 풀어야될지 bfs로 풀어야될지!!

걍 밑으로 늘어지면 dfs

뭔가 옆으로 늘어지면 bfs

이정도면 비기너로서의 탈출은 하고있는거같...?(아님말고)