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
}