# 2022-06-24

## 515. Find Largest Value in Each Tree Row

### Description

Given the `root` of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Example 1:

``````Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]``````

Example 2:

``````Input: root = [1,2,3]
Output: [1,3]``````

Constraints:

• The number of nodes in the tree will be in the range `[0, 10^4]`.

• `-2^31 <= Node.val <= 2^31 - 1`

### Solution

#### Approach #0: BFS

``````/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func largestValues(root *TreeNode) (ans []int) {
if root == nil {
return
}
queue := []*TreeNode{root}
for len(queue) > 0 {
size := len(queue)
big := queue[0].Val
for i := 0; i < size; i++ {
cell := queue[i]
big = max(big, cell.Val)
if cell.Left != nil {
queue = append(queue, cell.Left)
}
if cell.Right != nil {
queue = append(queue, cell.Right)
}
}
ans = append(ans, big)
queue = queue[size:]
}
return
}

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

#### Approach #1: DFS

``````/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func largestValues(root *TreeNode) (ans []int) {
if root == nil {
return
}
var dfs func(*TreeNode, int)
dfs = func(node *TreeNode, depth int) {
if node == nil {
return
}
if len(ans) <= depth {
ans = append(ans, node.Val)
} else {
ans[depth] = max(ans[depth], node.Val)
}
dfs(node.Left, depth+1)
dfs(node.Right, depth+1)
}
dfs(root, 0)
return
}

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

Last updated