LeetCode - Same Tree

wodnr_P·2023년 10월 15일

Same Tree binary tree leetcode 알고리즘

LeetCode Top Interview 150

목록 보기

31/32

⭐️ LeetCode 알고리즘 풀이 (with Python)

# Same Tree

[Quetion]

LeetCode 100. Same Tree

📌 접근법

[문제 이해]

두 Binary Tree p와 q가 같은지 확인

두 binary tree가 같은 형태, 같은 값을 가지는지 확인하기 위해서는 모든 노드를 순회해야한다고 생각했고, DFS와 BFS 중 BFS의 방법으로 접근했다.

p와 q를 순회하며 노드의 값을 저장하고, 만약 트리의 형태가 다르면 (ex: p는 왼쪽 q는 오른쪽에 하위 트리가 구성 되어있는 경우) 순회 결과를 다르게 하기 위해 0을 추가로 삽입했다.

💻 구현

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # p와 q가 모두 None이거나 한쪽만 None일 경우
        if p is None and q is None:
            return True
        if p is None or q is None:
            return False
        
        p_tree,q_tree=[],[]
        self.level_search(p, p_tree)  
        self.level_search(q, q_tree)
        return p_tree == q_tree
    
    # BFS
    def level_search(self, node, l):
        queue = [(node, 0)]
        while queue:
            node, level = queue.pop(0)
            if node is not None:
                l.append(node.val)
                if node.left:
                    queue.append((node.left, level+1))
                if node.right:
                    queue.append((node.right, level+1))
                else:
                    l.append(0)

Runtime: 32ms | Memory: 16.1MB
LeetCode 코드 중 Runtime 90%, Memory 94% 해당하는 결과

📌 로직 핵심

p와q 트리를 각각 BFS로 순회
node.left가 있고, node.right가 있는 조건과 더불어 0값을 추가하여 하위 트리 형태가 다르면 순회 결과를 다르게 하여 T or F 판단

📝 Same Tree 회고

모든 트리를 순회하고 마지막으로 두 리스트를 비교하기에 최악의 경우 O(N) 시간복잡도를 가지고, 방문한 노드의 값을 모두 저장해야하므로 O(N)의 공간복잡도를 가진다.
시간복잡도는 BFS, DFS 모두 모든 노드를 순회하기 때문에 O(N)으로서, 이미 최적화가 되었다고 생각하고 공간복잡도는 p_tree와 q_tree 리스트를 제거하는 방향으로 개선할 수 있을 것 같다.

# 개선 후
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None and q is None:
            return True
        if p is None or q is None:
            return False
        
        queue = [(p, q)]
        while queue:
            np, nq = queue.pop(0)
            if np is None and nq is None:
                continue
            
            elif np is None or nq is None or np.val != nq.val:
                return False
            
            queue.append((np.left, nq.left))
            queue.append((np.right, nq.right))
        return True