리트코드 - 872. Leaf-Similar Trees

https://leetcode.com/problems/leaf-similar-trees/description/?envType=study-plan-v2&envId=leetcode-75

Leaf-Similar Trees - LeetCode

두 개의 이진 트리의 노드가 주어졌을 때, 리프노드가 동일한 순서대로 있는지 확인하는 문제이다.

DFS 알고리즘을 활용하여 리프노드들을 모두 확인하는 방식으로 문제를 풀었다.

풀이 1

class Solution:
    def dfs(self, root_node, leaf_list): # O(1)
        if root_node.left:
            self.dfs(root_node.left, leaf_list)
        if root_node.right:
            self.dfs(root_node.right, leaf_list)
        elif root_node.left is None and root_node.right is None:
            return leaf_list.append(root_node.val)
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        root1_leaf, root2_leaf = [], []
        self.dfs(root1, root1_leaf) # O(n)
        self.dfs(root2, root2_leaf) # O(m)
        if len(root1_leaf) != len(root2_leaf): # O(1)
            return False
        else:
            for i in range(len(root1_leaf)): # O(n)
                if root1_leaf[i] != root2_leaf[i]: # O(1)
                    return False
        return True

각 이진 트리의 리프노드를 저장하는 배열들을 생성한 뒤 dfs를 통해 왼쪽부터 리프노드의 여부를 확인하고 배열에 넣도록 구현하였다.

• 시간 복잡도:
  • 두 트리에 대한 DFS 수행: 각각 O(n)과 O(m), 여기서 n과 m은 각각 두 트리의 노드 수이다.
  • 두 잎 리스트의 비교: O(k), 여기서 k는 리프 노드의 수다. 최악의 경우, 모든 노드가 잎 노드일 수 있으므로 O(n)이 될 수 있다.
  • 전체적으로, 시간 복잡도는 O(n + m)이다.
• 공간 복잡도:
  • 두 개의 잎 리스트 저장: 각각 O(n)과 O(m)의 공간을 차지한다.

풀이 2

# 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:
        def dfs(root):
            if not root: # O(1)
                return []
            if not root.left and not root.right: # O(1)
                return [root.val]
            
            return dfs(root.left) + dfs(root.right)
        
        return dfs(root1) == dfs(root2) # O(n) + O(m)

• 시간 복잡도: O(n + m). 여기서 n과 m은 각각 두 트리의 노드 수. 각 트리는 한 번씩만 순회한다.
• 공간 복잡도: O(n + m + h). 여기서 h는 두 트리 중 더 높은 트리의 높이다.
• 재귀 호출로 인한 스택 사용과 잎 노드 시퀀스를 저장이 주된 공간 사용 요인이 된다.
• 재귀 호출로만 잎 노드의 시퀀스를 구성하기 때문에 공간 사용이 상대적으로 줄어든다.

로직은 유사하나 상대적으로 코드가 더 명료하고 별도로 리스트를 할당하지 않고 재귀호출을 통해 리프노드의 시퀀스를 구성한다.