• 리프 노드 = 자식 노드가 없는 노드
• 문제가 이진트리니까 자식 노드로 left/right로 구현했지만, 트리가 BinaryTree 구조가 아니라면 여러 자식 노드를 가질 수 있으므로 자식 노드 프로퍼티에 배열 자료형을 사용한다.

DFS

# 이진트리를 정의하는 클래스(value는 자기자신, left나 right가 자식노드)
class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def find_leaf_nodes(root):
    if not root:
        return []
    
    if not root.left and not root.right:
        return [root.value]  # 현재 노드가 리프 노드인 경우, 해당 노드의 값을 리스트에 담아 반환
    
    # 현재 노드가 리프 노드가 아닌 경우, 왼쪽과 오른쪽 자식 노드에 대해 재귀적으로 함수를 호출
    leaves = []
    if root.left:
        leaves += find_leaf_nodes(root.left)
    if root.right:
        leaves += find_leaf_nodes(root.right)
    
    return leaves

BFS

from collections import deque

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

def find_leaf_nodes(root):
    if not root:
        return []
    
    queue = deque([root])
    leaf_nodes = []
    while queue:
        current_node = queue.popleft()
        if not current_node.left and not current_node.right:
            leaf_nodes.append(current_node.value)  # 리프 노드 발견
        if current_node.left:
            queue.append(current_node.left)
        if current_node.right:
            queue.append(current_node.right)
    
    return leaf_nodes

• 알고리즘의 시간복잡도는 O(n)보다 빠르게 만드는 것이 불가하나, 병렬처리나 메모리 최적화(캐시 활용)을 통해 실제 실행 시간을 빠르게 할 수는 있다.