1302. Deepest Leaves Sum

LeetCode

2021.05.30

簡単なグラフの問題。

幅優先探索と深さ優先探索の両方で解いてみた。

class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        from collections import deque
        q = deque()
        q.append(root)

        while q:
            l = len(q)
            ans = 0
            for _ in range(l):
                cur = q.popleft()
                ans += cur.val
                if cur.left is not None:
                    q.append(cur.left)
                if cur.right is not None:
                    q.append(cur.right)
        
        return ans

class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        self.ans = {}
        self.dfs(root, 0)

        return self.ans[max(self.ans)]
    
        
    def dfs(self, node, depth):
        if node is not None:
            if node.left is not None:
                self.dfs(node.left, depth+1)
            if node.right is not None:
                self.dfs(node.right, depth+1)
        
        if depth in self.ans:
            self.ans[depth] += node.val
        else:
            self.ans[depth] = node.val

参考