题目链接

力扣

题目描述

给定一棵二叉树的根节点 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

解题思路

dfs:存储一个当前高度值，在遍历到每个元素时与答案数组中的当前高度进行比较

bfs:维护一个结点数组，每一层遍历完后进行清空

Python使用了dfs，Go用了bfs

代码

Python

class Solution:
    def largestValues(self, root: TreeNode) -> list[int]:
        ans = []
 
        def dfs(node: TreeNode, curHeight: int) -> None:
            if not node:
                return
            if curHeight == len(ans):
                ans.append(node.val)
            else:
                ans[curHeight] = max(ans[curHeight], node.val)
            dfs(node.left, curHeight + 1)
            dfs(node.right, curHeight + 1)
        dfs(root, 0)
        return ans

Go

func largestValues(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	ans := []int{}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		curMax := math.MinInt32
		tmp := queue
		queue = nil
		for _, node := range tmp {
			if node.Val > curMax {
				curMax = node.Val
			}
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		ans = append(ans, curMax)
	}
	return ans
}