🍣

LeetCode 1161. Maximum Level Sum of a Binary Tree - 木探索の再帰とキュー

2025/09/11に公開

LeetCode

tech

1161. Maximum Level Sum of a Binary Tree

Insutituion

深さ優先探索を用いて木走査する。

ruby

def max_level_sum(root)
   hash = {}
   dfs = -> (node, level) {
      if node
        hash[level] ||= []
        hash[level].push(node.val)
        dfs.call(node.right, level+1)
        dfs.call(node.left, level+1)
      end
   }
   dfs.call(root, 0)
  
   max_level = 0
   max = hash[0].sum
   hash.each do |level, arr|
     if arr.sum > max
       max = arr.sum
       max_level = level
     end
   end
   return max_level + 1
end

改善点:
- ①各値をarrayで保持するのではなく、合計値のみを保存することでsumの最終計算が不要となる。
- ②rootの起点を1にすることで、問題と起点を合わせる

def max_level_sum(root)
   hash = {}
   dfs = -> (node, level) {
      if node
        hash[level] ||= 0
        hash[level] += node.val
        dfs.call(node.right, level+1)
        dfs.call(node.left, level+1)
      end
   }
   dfs.call(root, 1)
  
   hash.max_by { |k, v| v }[0]
end

Approach①

深さ優先探索アプローチ

python

max関数にkeyを指定して最大値となるkeyを取得する

>>> sums = {}
>>> sums[1] = 100
>>> sums[2] = 200
>>> max(sums, key=sums.get)
2

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
      sums = {}
      def dfs(node, level):
        nonlocal sums
        if node:
          val = sums.get(level, 0)
          sums[level] = val + node.val
          dfs(node.left, level+1)
          dfs(node.right, level+1)

      dfs(root, 1)

      return max(sums, key=sums.get)

typescript

キーとペアを扱うためにMap<K,V>を利用する　https://typescriptbook.jp/reference/builtin-api/map

function maxLevelSum(root: TreeNode | null): number {
    let sums = new Map<number, number>()

    function dfs(node: TreeNode | null, level: number){
      if (node) {
        const val = sums.get(level) || 0;
        sums.set(level, val + node.val);
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
      }
    }

    dfs(root, 1)

    let maxLevel: number = 0
    let maxSum: number = -Infinity
    for (const [level, sum] of sums.entries()) {
      if (sum > maxSum){
        maxLevel = level
        maxSum = sum
      }
    }
    return maxLevel
};

golang

func maxLevelSum(root *TreeNode) int {
    var sums = make(map[int]int)

    var dfs func(node *TreeNode, level int)
    dfs = func(node *TreeNode, level int){
      if node != nil {
        sums[level] += node.Val
        dfs(node.Left, level+1)
        dfs(node.Right, level+1)
      }
    }

    dfs(root, 1)

    var maxLevel int
    var maxSum int = math.MinInt64
    for level, sum := range sums {
      if sum > maxSum {
        maxLevel = level
        maxSum = sum
      }
    }
    return maxLevel
}

Approach②

幅優先探索アプローチ

ruby

def max_level_sum(root)

  queue = [root]

  max_level = 1
  max_sum = -Float::INFINITY
  current_level = 1

  while !queue.empty?
    # 現在のレベルにあるノードだけを処理する。queue.eachを使うと、ループ中にキューのサイズが変わってしまい、正しく動作しない
    level_size = queue.length

    current_level_sum = 0
    level_size.times do
      # キューの先頭からノードを一つ取り除く
      node = queue.shift
      current_level_sum += node.val
      queue << node.left if node.left
      queue << node.right if node.right
    end

    if current_level_sum > max_sum
      max_sum = current_level_sum
      max_level = current_level
    end
    current_level += 1
  end
  max_level
end

Array#shiftの計算量はO(n)
- 配列の先頭から要素を削除すると、残りのすべての要素をメモリ上で1つずつ前にずらす必要がある

python

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
      queue = collections.deque()
      queue.append(root)

      max_level= 1
      max_sum = float('-inf')

      current_level = 1

      while queue:
        current_level_sum = 0
        for _ in range(len(queue)):
          node = queue.popleft()
          current_level_sum += node.val
          if node.left:
            queue.append(node.left)
          if node.right:
            queue.append(node.right)

        if current_level_sum > max_sum:
          max_sum = current_level_sum
          max_level = current_level

        current_level += 1

      return max_level

キューの先頭から要素を取り出すときは、collection.dequeをキューとして利用する。
collection.dequeの計算量はO(1)
- https://docs.python.org/ja/3/library/collections.html#collections.deque

typescript

function maxLevelSum(root: TreeNode | null): number {
    let queue: (TreeNode | null)[] = [root]
    let max_level: number
    let max_sum: number = -Infinity

    let current_level: number = 1

    while(queue.length>0) {
      let current_level_sum: number = 0
      let level_size: number = queue.length
      for(let i=0; i < level_size; i++){
        let node: TreeNode = queue.shift()
        current_level_sum += node.val
        if (node.left) { queue.push(node.left)}
        if (node.right) { queue.push(node.right )}

      }
      if (current_level_sum > max_sum){
        max_sum = current_level_sum
        max_level = current_level
      }
      current_level++
    }
    return max_level
};

golang

func maxLevelSum(root *TreeNode) int {
    var queue = []*TreeNode{root}
    var max_level int
    var max_sum int = math.MinInt64 

    var current_level int = 1

    for len(queue)>0 {
      var current_level_sum int = 0
      var queue_length = len(queue)
      for i := 0; i < queue_length; i++ {
        node := queue[0]
        queue = queue[1:]
        current_level_sum += node.Val
        if node.Left != nil { queue = append(queue, node.Left)}
        if node.Right != nil { queue = append(queue, node.Right)}
      }

      if current_level_sum > max_sum{
        max_sum = current_level_sum
        max_level = current_level
      }

      current_level++
    }
    return max_level
}

学習のポイント

深さ優先探索
- 再帰関数を用いて実装する
- メモリ使用量は、木の高さ（深さ）に依存するため、深い木ではスタックオーバーフローのリスクがある。
幅優先探索
- キューを用いて実装する

1161. Maximum Level Sum of a Binary Tree

Insutituion

Approach①

Approach②

学習のポイント

Discussion