Kimi也翻车了，9.11比9.9大，威胁都没用。。

现在类似于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算法文档 。