0515. Find Largest Value in Each Tree Row

# 515. Find Largest Value in Each Tree Row#

## 题目 #

You need to find the largest value in each row of a binary tree.

Example:

``````Input:

1
/ \
3   2
/ \   \
5   3   9

Output: [1, 3, 9]
``````

## 解题思路 #

• 给出一个二叉树，要求依次输出每行的最大值
• 用 BFS 层序遍历，将每层排序取出最大值。改进的做法是遍历中不断更新每层的最大值。

## 代码 #

``````
package leetcode

import (
"math"
"sort"
)

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/

// 解法一 层序遍历二叉树，再将每层排序取出最大值
func largestValues(root *TreeNode) []int {
tmp := levelOrder(root)
res := []int{}
for i := 0; i < len(tmp); i++ {
sort.Ints(tmp[i])
res = append(res, tmp[i][len(tmp[i])-1])
}
return res
}

// 解法二 层序遍历二叉树，遍历过程中不断更新最大值
func largestValues1(root *TreeNode) []int {
if root == nil {
return []int{}
}
q := []*TreeNode{root}
var res []int
for len(q) > 0 {
qlen := len(q)
max := math.MinInt32
for i := 0; i < qlen; i++ {
node := q[0]
q = q[1:]
if node.Val > max {
max = node.Val
}
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
res = append(res, max)
}
return res
}

// 解法三 深度遍历二叉树
func largestValues3(root *TreeNode) []int {
var res []int
var dfs func(root *TreeNode, level int)
dfs = func(root *TreeNode, level int) {
if root == nil {
return
}
if len(res) == level {
res = append(res, root.Val)
}
if res[level] < root.Val {
res[level] = root.Val
}

dfs(root.Right, level+1)
dfs(root.Left, level+1)
}
dfs(root, 0)
return res
}

``````

Apr 8, 2023