Java教程

0515-在每个树行中找到最大值

本文主要是介绍0515-在每个树行中找到最大值,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

给定一棵二叉树的根节点 root ,请找出该二叉树中每一层的最大值。

示例1:

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:
1
/
3 2
/ \ \
5 3 9
示例2:

输入: root = [1,2,3]
输出: [1,3]
解释:
1
/
2 3
示例3:

输入: root = [1]
输出: [1]
示例4:

输入: root = [1,null,2]
输出: [1,2]
解释:
  1
 
  2
示例5:

输入: root = []
输出: []

提示:

二叉树的节点个数的范围是 [0,104]
-231 <= Node.val <= 231 - 1

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row

python

# 0515.二叉树的每个树行的最大值
class Solution:
    def levelOrder(self, root: TreeNode) -> [int]:
        """
        迭代法:双端队列,每次把单层的节点遍历出队列,另外将对应的左右节点加入队列
        :param root:
        :return:
        """
        results = []
        if not root:
            return results

        from collections import deque
        queue = deque([root]) # 初始化队列

        while queue:
            size = len(queue) # 遍历队列单层长度
            res = [] # 每次遍历时初始化加入结果集中的列表
            for _ in range(size):
                cur = queue.popleft() # 通过size控制遍历次数
                res.append(cur.val) # 加入结果集中
                if cur.left: # 添加当前pop节点的左节点进入队列
                    queue.append(cur.left)
                if cur.right: # 添加当前pop节点的右节点进入队列
                    queue.append(cur.right)
            results.append(max(res)) # 当层中的所有节点的值放入list中

        return results

golang

package binaryTree

import (
	"container/list"
	"math"
)

// 迭代遍历
func largestValues(root *TreeNode) []int {
	var res =  [][]int{}
	if root == nil { // 空时返回
		return nil
	}
	queue := list.New() // 队列初始化
	queue.PushBack(root)
	var tmpArr []int
	for queue.Len() > 0 {
		length := queue.Len()
		for i:=0;i<length;i++ { // 遍历当层的节点
			node := queue.Remove(queue.Front()).(*TreeNode) // 当次节点
			if node.Left != nil { // 节点的左节点入队
				queue.PushBack(node.Left)
			}
			if node.Right != nil { // 节点的右节点入队
				queue.PushBack(node.Right)
			}
			tmpArr = append(tmpArr, node.Val) // 节点值加入结果集
		}
		res = append(res, tmpArr)
		tmpArr = []int{}
	}
	// 处理层max
	finalRes := []int{}
	for i:=0;i<len(res);i++ {
		finalRes = append(finalRes, max(res[i]))
	}
	return finalRes
}

func max(arr []int) int {
	max := math.MinInt32
	for i:=0;i<len(arr);i++ {
		if arr[i] > max {
			max = arr[i]
		}
	}
	return max
}


这篇关于0515-在每个树行中找到最大值的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!