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
}
