99클럽 코테 스터디 10일차 TIL + DFS

 

🔗 LeetCode - 1302. Deepest Leaves Sum

😇 헤매지 않는 날이 없군!

우선 첫번째로 문제를 잘못 이해해서 node 자체가 들어오는 지 몰라서... int array가 들어오면 그것을 node로 만들고 tree로 예쁘게 만들어 줬는데!! 이미 treenode 형태로 input이 들어와서 쓸모가 없어짐....

코드 보기

# Definition for a binary tree node.
  import queue
  from collections import deque


  class TreeNode:
      def __init__(self, val=0, left=None, right=None):
          self.val = val
          self.left = left
          self.right = right


  class Solution:
      def make_tree(self, root):
          q = queue.Queue()
          q.put(root)
          while not q.empty() and self.nums:
              root = q.get()
              if root.val:
                  left = TreeNode()
                  left.val = self.nums.popleft().val
                  root.left = left
                  right = TreeNode()
                  right.val = self.nums.popleft()
                  root.right = right
                  q.put(left)
                  q.put(right)

      def DFS(self, root, end_nodes, height):
          if root:
              self.DFS(root.left, end_nodes, height + 1)
              self.DFS(root.right, end_nodes, height + 1)
              if root.val:
                  end_nodes.append([height, root.val])

      def deepestLeavesSum(self, root):
          self.nums = deque(nums)
          self.length = len(nums)
          root = TreeNode()
          root.val = self.nums.popleft()
          self.make_tree(root)

          end_nodes = []
          self.DFS(root, end_nodes, 0)
          end_nodes = sorted(end_nodes, key=lambda sub_list: sub_list[0], reverse=True)
          max_height = max(end_nodes)[0]
          answer = 0
          for nodes in end_nodes:
              if nodes[0] == max_height:
                  answer += nodes[1]
          return answer


  DFS = Solution()
  root =[6,7,8,2,7,1,3,9,None,1,4,None,None,None,5]
  print(DFS.deepestLeavesSum(root))

 

그래서 노드 새로 배정하는 과정을 없에고 바로 재귀 DFS를 실행했더니 통과했으나 속도가 너무 느렸다...

코드 보기

# Definition for a binary tree node.
import queue
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def make_tree(self, root):
        q = queue.Queue()
        q.put(root)
        while not q.empty() and self.nums:
            root = q.get()
            if root.val:
                left = TreeNode()
                left.val = self.nums.popleft().val
                root.left = left
                right = TreeNode()
                right.val = self.nums.popleft()
                root.right = right
                q.put(left)
                q.put(right)

    def DFS(self, root, end_nodes, height):
        if root:
            self.DFS(root.left, end_nodes, height + 1)
            self.DFS(root.right, end_nodes, height + 1)
            if root.val:
                end_nodes.append([height, root.val])

    def deepestLeavesSum(self, root):
        # self.nums = deque(nums)
        # self.length = len(nums)
        # root = TreeNode()
        # root.val = self.nums.popleft()
        # self.make_tree(root)
        end_nodes = []
        self.DFS(root, end_nodes, 0)
        end_nodes = sorted(end_nodes, key=lambda sub_list: sub_list[0], reverse=True)
        max_height = max(end_nodes)[0]
        answer = 0
        for nodes in end_nodes:
            if nodes[0] == max_height:
                answer += nodes[1]
        return answer

 

그래서 solution들을 보다가 tree 만들때 쓴 것처럼 queue를 사용해 DFS를 돌면서 각 depth 별로 node값들을 다 더해 dictionary에 저장하는 방법이 있어 따라해 봤다. 

# Definition for a binary tree node.
import queue
from collections import deque


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):
        q = deque()
        q.append((root,0))
        node_dict = {}
        while q:
            node, depth = q.popleft()
            if depth in node_dict:
                node_dict[depth] += node.val
            else:
                node_dict[depth] = node.val
            if node.left:
                q.append((node.left, depth + 1))
            if node.right:
                q.append((node.right, depth + 1))
        return list(node_dict.values())[-1]

 

 오늘도 이렇게 삽질을 했지만 여러가지 배워간다 🤣