2583. 二叉树中的第 K 大层和

二叉树中的第 K 大层和

• 难度: medium
• 原始链接: https://leetcode.cn/problems/kth-largest-sum-in-a-binary-tree
• 标签: 层序遍历

解法一: 广度优先遍历

go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthLargestLevelSum(root *TreeNode, k int) int64 {
  queue := []*TreeNode{root}
  var sumArr []int64
  for len(queue) > 0 {
    size := len(queue)
    var sum int64
    for i := 0; i < size; i++ {
      node := queue[i]
      sum += int64(node.Val)
      if node.Left != nil {
        queue = append(queue, node.Left)
      }
      if node.Right != nil {
        queue = append(queue, node.Right)
      }
    }
    queue = queue[size:]
    sumArr = append(sumArr, sum)
  }
  if len(sumArr) < k {
    return -1
  }
  sort.Slice(sumArr, func(i, j int) bool {
    return sumArr[i] >= sumArr[j]
  })
  return sumArr[k-1]
}

解法二: 深度优先遍历

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthLargestLevelSum(root *TreeNode, k int) int64 {
  var sumArr []int64
  var dfs func(*TreeNode, int)
  dfs = func(node *TreeNode, depth int) {
    if node == nil {
      return
    }
    if len(sumArr) <= depth {
      sumArr = append(sumArr, 0)
    }
    sumArr[depth] += int64(node.Val)
    dfs(node.Left, depth+1)
    dfs(node.Right, depth+1)
  }
  dfs(root, 0)
  if len(sumArr) < k {
    return -1
  }
  sort.Slice(sumArr, func(i, j int) bool {
    return sumArr[i] >= sumArr[j]
  })
  return sumArr[k-1]
}