现在类似于Chatgpt这种人工智能大模型太多了，使用它们确实能提高我们的工作效率。今天我使用了8个常用的大模型问了同样一个问题：9.11和9.9哪个大，结果只有Kimi给出了错误的回复，我甚至威胁让它重新思考一下，结果它还是给出错误答案。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第515题：在每个树行中找最大值。
问题描述
来源：LeetCode第515题
难度：中等
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1：
输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9]
示例2：
输入: root = [1,2,3] 输出: [1,3]
二叉树的节点个数的范围是 [0,10^4]
-2^31 <= Node.val <= 2^31 - 1
问题分析
这题是让计算二叉树中每行的最大值，我们只需要一行一行的遍历，即可找出每行中的最大值，这个就是BFS遍历。
除了BFS以外我们还可以使用DFS，如果第一次到达某一层的时候，只需要把这个节点值保存下来即可，否则如果不是第一次达到，就和之前的值比较，保存最大的。
比如示例 1 中第一次到达第 3 层，首先访问的是节点 5 ，把它保存下来。当访问到节点 3 和 9 的时候它们也是在第 3 层，也就是说第 3 层已经保存过了，所以要和保存过的值比较，记录最大的。
JAVA：
public List largestValues (TreeNode root) {
List
ans = new ArrayList<>(); dfs(root, ans, 0); return ans; } private void dfs(TreeNode root, List ans, int level) { if (root == null) return; // 如果第一次走到下一层直接加入到集合中 if (level == ans.size()) { ans.add(root.val); } else { // 如果之前保存过，要取最大值保存 ans.set(level, Math.max(ans.get(level), root.val)); } // 下面两行是递归左右子树 dfs(root.left, ans, level + 1); dfs(root.right, ans, level + 1); }C++：
public:
vector
largestValues(TreeNode *root) { vector
ans; dfs(root, ans, 0); return ans; } void dfs(TreeNode *root, vector
&ans, int level) { if (root == nullptr) return; // 如果第一次走到下一层直接加入到集合中 if (level == ans.size()) { ans.push_back(root->val); } else {// 如果之前保存过，要取最大值保存 ans[level] = max(ans[level], root->val); } // 下面两行是递归左右子树 dfs(root->left, ans, level + 1); dfs(root->right, ans, level + 1); }
Python：
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
def dfs(node, level):
if not node:
return
# 如果第一次走到下一层直接加入到集合中
if level == len(ans):
ans.append(node.val)
else: # 如果之前保存过，要取最大值保存
ans[level] = max(ans[level], node.val)
# 下面两行是递归左右子树
dfs(node.left, level + 1)
dfs(node.right, level + 1)
ans = []
dfs(root, 0)
return ans笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴