leetcode算法: Find Largest Value in Each Tree Row
2023-09-27 14:28:47 时间
'''
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]
'''
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
这道题描述的是:
给我们一颗二叉树的根节点,返回每一层最大值的数组
思想:
广度优先遍历,把每一层最大值放入结果列表
python实现:
1 class Solution(object):
2 def largestValues(self, root):
3 """
4 :type root: TreeNode
5 :rtype: List[int]
6 """
7 if not root:
8 return []
9 levels = [[root]]
10 values = [[root.val]]
11 for level in levels:
12 next_level = []
13 value = []
14 for node in level:
15 if node.left is not None:
16 next_level.append(node.left)
17 value.append(node.left.val)
18 if node.right is not None:
19 next_level.append(node.right)
20 value.append(node.right.val)
21 if next_level:
22 levels.append(next_level)
23 values.append(value)
24 res = []
25 for v in values:
26 res.append(max(v))
27 return res
精简一下代码:
1 class Solution(object):
2 def largestValues(self, root):
3 """
4 :type root: TreeNode
5 :rtype: List[int]
6 """
7 values = []
8 level = [root]
9 while any(level):
10 values.append( max( [i.val for i in level] ) )
11 level = [child for node in level for child in [node.left, node.right ] if child is not None]
12 return values
相关文章
- 【LeetCode】回文子串 [M](Manacher算法)
- 【LeetCode】分割等和子集 [M](动态规划)
- 【LeetCode】分割回文串 [M](深度优先遍历)
- 【LeetCode】合并区间 [M](贪心)
- 【LeetCode】找出字符串中第一个匹配项的下标 [M](KMP算法)
- 【LeetCode】最长回文子串 [M](Manacher算法)
- 【LeetCode】三个无重叠子数组的最大和 [H](动态规划)
- 【LeetCode】回文对 [H](Manacher算法)
- 【LeetCode】自由之路 [H](记忆化搜索)
- leetcode 2 Add Two Numbers
- [Java/LeetCode]算法练习:二进制间距(868/simple)
- 2023-02-23 leetcode-查找算法-TwoSum-思考
- LeetCode 算法刷题目录 (Java)
- LeetCode_贪心算法_简单_409.最长回文串
- LeetCode_位运算_简单_231.2 的幂
- LeetCode_贪心算法_中等_55.跳跃游戏
- LeetCode_Boyer-Moore 投票算法_中等_229.求众数 II
- LRU算法&&LeetCode解题报告
- Leetcode中的Dijkstra算法
- 「LeetCode」剑指 Offer 40. 最小的k个数
- 【算法】动态规划 ⑦ ( LeetCode 55. 跳跃游戏 | 算法分析 | 代码示例 )
- 【算法】动态规划 ⑤ ( LeetCode 63.不同路径 II | 问题分析 | 动态规划算法设计 | 代码示例 )
- [LeetCode] 362. Design Hit Counter 设计点击计数器
- [LeetCode] 454. 4Sum II 四数之和II
- [LeetCode] 265. Paint House II 粉刷房子
- leetcode算法: Find All Duplicates in an Array
- leetcode算法:Reshape the Matrix
- 前端面试必备-40道LeetCode经典面试算法题
- leetcode 101 对称二叉树