99클럽 코테 스터디 13일차 TIL + Tree Depth-First Search Breadth-First Search Binary Tree : deepest-leaves-sum

문제

링크텍스트

풀이

from typing import Optional
# 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:
        q0 = [root]
        while True:
            q = []
            for qi in q0:
                if qi.left:
                    if qi.left.val:
                        q.append(qi.left)
                if qi.right:
                    if qi.right.val:
                        q.append(qi.right)
            if not q:
                break
            q0 = q.copy()
        a = sum([i.val for i in q0 if i.val])
        return a

from collections import deque
class nt:
    def __init__(self, root0):
        self.n = len(root0)
        rs = []
        i0 = 0
        for i in range(self.n):
            if root0[i]:
                i0 += 1
            rs.append(TreeNode(root0[i]))
        self.n0 = i0
        i0 = 1
        for i in range(self.n):
            if rs[i].val:
                rs[i].left = rs[i0]
                rs[i].right = rs[i0+1]
                i0 += 2
            if i0 == self.n:
                break
        self.n1 = i0
        self.r = rs[0]
        
    def pr(self):
        print(f'n: {self.n}, n0: {self.n0}')
        q = deque()
        q.append(self.r)
        cnt = 0
        while q:
            q0 = q.copy()
            q.clear()
            for qi in q0:
                s = f'level = {cnt:4}; p: '
                s += f'{qi.val:4}; ' if qi.val is not None else "None"
                if qi.left:
                    q.append(qi.left)
                    s += f'l: {qi.left.val:4}; ' if qi.left.val is not None else 'l: None; '
                if qi.right:
                    q.append(qi.right)
                    s += f'l: {qi.right.val:4}; ' if qi.right.val is not None else 'l: None'
                print(s)
            cnt += 1

for i in range(2):
    null = None
    print(f'test case: {i}')
    if i == 0:
        root0 = [1,2,3,4,5,null,6,7,null,null,null,null,8]
        Output = 15
    if i == 1:
        root0 = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
        Output = 19

    nt_i = nt(root0)
    # nt_i.pr()
    sol = Solution()
    a = sol.deepestLeavesSum(nt_i.r)
    print(a)
    print(Output)

• class TreeNode 가 주어집니다.
• 예제 입력 list를 TreeNode로 변환하는 class nt를 작성합니다.
  • class nt
    • n: 주어진 list의 크기
    • n0: 주어진 list의 요소 중 null 이 아닌 요수의 수
      • 여기서는 python에 맞추어 null = None 으로 하여 처리합니다.
    • 초기화
      • 모든 list의 값을 TreeNode 로 전환합니다.
      • 규칙에 맞추어 left와 right를 연결합니다.
    • pr() 함수는 instance내 연결 관계를 level 별로 프린트 합니다.

      • 예: level = 2; parent 값 = 4; left 값 = 7; right 값 = None;

        level =    2; p =    4; l =    7; l = None;

• Solution 내, deepestLeavesSum() 함수에서 최하단 node 들의 값의 합을 구합니다.
  • 처음에는 습관적으로 deque를 썼으나 큰 의미가 없는 듯하여 list로 바꾸었습니다.
  • 시작은 root의 list입니다. q0 = [root]
  • q0 내 모든 TreeNode 요쇼에 대하여, left와 right를 새로운 list q에 넣습니다.
    • 단, 그 값이 None이 아닌 경우만입니다.
  • q0 = q.copy() 로 하여 반복합니다.
  • 더 이상 q에 넣을 요소가 없으면 멈추고 (q0 = q.copy() 하기 전에 !!!)
    • q0 내 모든 요소의 값을 합하여 return 합니다.

결과