515. Find Largest Value in Each Tree Row #

Problem #

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]

Problem Summary #

Find the largest value in each row of a binary tree.

Solution Approach #

Given a binary tree, output the maximum value of each row in order.
Use BFS level-order traversal, sort each level and take out the maximum value. An improved approach is to continuously update the maximum value of each level during traversal.

Code #


package leetcode

import (
	"math"
	"sort"
)

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

// Solution 1: Level-order traverse the binary tree, then sort each level to get the maximum value
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
}

// Solution 2: Level-order traverse the binary tree, continuously updating the maximum value during traversal
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
}

// Solution 3: Depth-first traverse the binary tree
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
}