剑指 Offer II 044. 二叉树每层的最大值
给定一棵二叉树的根节点 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
注意：本题与主站 515 题相同： https://leetcode.cn/problems/find-largest-value-in-each-tree-row/
原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 5.4 MB, 提交时间: 2022-11-17 16:27:07
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func largestValues(root *TreeNode) (ans []int) {
var dfs func(*TreeNode, int)
dfs = func(node *TreeNode, curHeight int) {
if node == nil {
return
}
if curHeight == len(ans) {
ans = append(ans, node.Val)
} else {
ans[curHeight] = max(ans[curHeight], node.Val)
}
dfs(node.Left, curHeight+1)
dfs(node.Right, curHeight+1)
}
dfs(root, 0)
return
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
golang 解法, 执行用时: 4 ms, 内存消耗: 5.6 MB, 提交时间: 2022-11-17 16:26:47
/**
* 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
}
q := []*TreeNode{root}
for len(q) > 0 {
maxVal := math.MinInt32
tmp := q
q = nil
for _, node := range tmp {
maxVal = max(maxVal, node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
ans = append(ans, maxVal)
}
return
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
python3 解法, 执行用时: 48 ms, 内存消耗: 17.7 MB, 提交时间: 2022-11-17 16:26:27
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
'''
我们也可以用「广度优先搜索」的方法来解决这道题目。「广度优先搜索」中的队列里存放的是「当前层的所有节点」。
每次拓展下一层的时候，不同于「广度优先搜索」的每次只从队列里拿出一个节点，
我们把当前队列中的全部节点拿出来进行拓展，这样能保证每次拓展完的时候队列里存放的是下一层的所有节点，
即我们是一层一层地进行拓展，然后每一层我们用 maxVal 来标记该层节点的最大值。
当该层全部节点都处理完后，maxVal 就是该层全部节点中的最大值。
'''
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
if root is None:
return []
ans = []
q = [root]
while q:
maxVal = -inf
tmp = q
q = []
for node in tmp:
maxVal = max(maxVal, node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(maxVal)
return ans
python3 解法, 执行用时: 64 ms, 内存消耗: 18.2 MB, 提交时间: 2022-11-17 16:25:05
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
'''
我们用树的「先序遍历」来进行「深度优先搜索」处理，并用 curHeight 来标记遍历到的当前节点的高度。
当遍历到 curHeight 高度的节点就判断是否更新该层节点的最大值。
'''
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
ans = []
def dfs(node: TreeNode, curHeight: int) -> None:
if node is None:
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