[Leetcode/Tree] 872. Leaf-Similar Trees

# 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 leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        # 주어진 트리의 리프 노드(leaf node) 값을 순서대로 가져오는 함수
        def get_leaf_sequence(root: Optional[TreeNode]) -> List[int]:
            leaf_nodes = [] # 리프 노드 값을 저장할 리스트

            # 깊이 우선 탐색(DFS)을 수행하는 재귀 함수
            def dfs(node: Optional[TreeNode]):
                if not node:
                    return
                if not node.left and not node.right: # 리프 노드인 경우
                    leaf_nodes.append(node.val) # 리프 노드의 값을 리스트에 추가
                dfs(node.left) # 왼쪽 자식 노드 탐색
                dfs(node.right) # 오른쪽 자식 노드 탐색
            
            dfs(root) # 루트 노드부터 DFS 시작
            return leaf_nodes # 리프 노드 값 리스트 반환
        
         # 두 트리의 리프 노드 값 리스트를 비교하여 동일한지 확인
        return get_leaf_sequence(root1) == get_leaf_sequence(root2)