题目

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9]

解释:

1

/

3 2

/

5 3 9

示例2：输入: root = [1,2,3] 输出: [1,3]

解释:

1

/

2 3

示例3：输入: root = [1] 输出: [1]

示例4：输入: root = [1,null,2] 输出: [1,2]

解释:

1

2

示例5：输入: root = [] 输出: []

提示：二叉树的节点个数的范围是 [0,104]

-231 <= Node.val <= 231 - 1

注意：本题与主站 515 题相同：

解题思路分析

1、层序遍历；时间复杂度O(n)，空间复杂度O(n)

func largestValues(root *TreeNode) []int {
   res := make([]int, 0)
   if root == nil {
      return res
   }
   queue := make([]*TreeNode, 0)
   queue = append(queue, root)
   for len(queue) > 0 {
      length := len(queue)
      maxValue := math.MinInt32
      for i := 0; i < length; i++ {
         if queue[i].Left != nil {
            queue = append(queue, queue[i].Left)
         }
         if queue[i].Right != nil {
            queue = append(queue, queue[i].Right)
         }
         if maxValue < queue[i].Val {
            maxValue = queue[i].Val
         }
      }
      res = append(res, maxValue)
      queue = queue[length:]
   }
   return res
}

2、递归；时间复杂度O(n)，空间复杂度O(n)

var res []int

func largestValues(root *TreeNode) []int {
   res = make([]int, 0)
   if root == nil {
      return res
   }
   dfs(root, 0)
   return res
}

func dfs(root *TreeNode, level int) {
   if root == nil {
      return
   }
   if level >= len(res) {
      res = append(res, math.MinInt32)
   }
   res[level] = max(res[level], root.Val)
   dfs(root.Left, level+1)
   dfs(root.Right, level+1)
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

总结

Medium题目，题目同leetcode 515.在每个树行中找最大值