[99클럽 코테 스터디 13일차 TIL] LeetCode | 1302. Deepest Leaves Sum

 

 

Problem

https://leetcode.com/problems/deepest-leaves-sum/description/

 

Sol

트리 가장 깊은 depth의 leaf node의 값을 더해주면 되는 문제

---

✔ Answer

[DFS]

문제를 보고 노드의 수를 통해 트리의 깊이인 h를 구하고 해당 h에 해당하는  node들을 더하려고 DFS 관점에서 접근해보았습니다. 더 효율적으로 풀 수 있을 것 같습니다..

# 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:
    # 1. deepest depth 구하기
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
    
    # 2. deepest leaf 노드들 값 더하기
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        max_depth = self.maxDepth(root)
        
        # DFS
        def dfs(node: Optional[TreeNode], depth: int) -> int:
            if not node:
                return 0
            
            # deepest depth의 leafnode
            if depth == max_depth:
                return node.val
            
            # recursion
            return dfs(node.left, depth + 1) + dfs(node.right, depth + 1)
        
        # 루트부터 가장 깊은곳까지
        return dfs(root, 1)

 

 

[BFS]

그리고 BFS로 구현했을 때 성능차이가 날지 궁금했습니다. 저번 문제에서 deque를 사용하여 구현해보았기 때문에 이번에는 list를 queue에 저장하는 형식으로 BFS를 구현해보았습니다.  굳이 싶은 부분도 있었지만 일단 .. 진행 ..

# 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 deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        # BFS
        queue = [root]

        while queue:
            leaves_sum = 0
            # 현재 level node 수
            level_size = len(queue)

            # 현재 level node 처리
            for _ in range(level_size):
                node = queue.pop(0)
                leaves_sum += node.val

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        return leaves_sum

 

 

DFS vs. BFS 성능 비교

좌 DFS, 우 BFS

사실 두 알고리즘을 비교할 수 있게 구현한지도 모르겠지만 제가 구현한 코드에서 보이는 성능 차이는 이러했습니다.

 

너무 꼬리칸에 있는 것 같아서 deque를 사용해 다시 풀어보았습니다. deque를 사용한 BFS에서는 queue연산에 대해 O(1)에 대한 시간 복잡도를 가지므로 더 빠른 실행이 가능했습니다.👍

from collections import deque

class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        # deque 사용
        queue = deque([root])
        leaves_sum = 0

        while queue:
            level_size = len(queue)
            leaves_sum = 0

            for _ in range(level_size):
            	# pop(0) 대신 popleft() 사용
                node = queue.popleft()
                leaves_sum += node.val

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        return leaves_sum

 

🤔 deque를 사용했을 때 효과 | pop(0) popleft()

• pop(0) : 리스트에서 첫 번째 요소를 꺼내는 연산
  • 리스트의 나머지 요소들을 한 칸씩 왼쪽으로 이동시켜야 함
  • 리스트의 길이에 비례하는 시간 소요
  • O(n)
• popleft() : deque에서 첫 번재 요소를 꺼내는 연산
  • deque : 이중 연결 리스트
  • 양쪽 끝에서의 삽입 삭제가 모두 O(1) 에 가능!
  • O(1)

---

 

💬 작심삼일! 내일도 킵고잉~'0'