文心一言宣布4月1日起全面免费。。

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

最近文心一言宣布4月1日免费了，这确实是一个好消息，虽然百度的产品负面评价比较多，主要是百度搜索时候的广告和网盘限速，但百度在搜索这块的技术还是有的。

百度太急功近利了，AI大模型一出来的时候就想收费，我常用的AI搜索有Kimi，文心一言，腾讯元宝，豆包，讯飞星火，通义千问，天工超能……有十几个，目前也只有文心一言敢收费。目前文心一言4.0还是收费的，只有3.5是免费的。之前想充值体验一下的，这次正好免费了，到时候看下效果怎么样？不过我觉得这次免费应该是受DeepSeek的影响，文心一言再不免费，估计用户要全部流失了。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第99题：恢复二叉搜索树。

问题描述

来源：LeetCode第99题

难度：中等

给你二叉搜索树的根节点 root ，该树中的 恰好两个节点的值被错误地交换 。请在不改变其结构的情况下，恢复这棵树 。

示例1：

输入：root = [1,3,null,null,2] 输出：[3,1,null,null,2] 解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例2：

输入：root = [3,1,4,null,null,2] 输出：[2,1,4,null,null,3] 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

• 树上节点的数目在范围 [2, 1000] 内

• -2^31 <= Node.val <= 2^31 - 1

问题分析

这题说的是一颗二叉搜索树的两个节点被错误的交换，让我们恢复这棵二叉搜索树。

我们知道 二叉搜索树的中序遍历结果是有序的 ，我们只需要对这棵二叉搜索树进行中序遍历，就可以找出这两个错误的节点，最后交换它们的值即可。

比如正常二叉搜索树中遍历的结果是:[1,2,3,4,5]，是有序的，由于错误交换两个节点，比如2和4交换，导致中序遍历的结果变成[1,4,3,2,5]，在中序遍历的时候每次都会和前一个节点值比较，如果当前节点比前一个节点值小，说明出现了错误的节点。

比如第一次3比4小，说明4(pre)是第一个错误节点，第二次是2比3小，说明2(cur)是第二个错误节点，最后交换它们的值即可。

JAVA：

private TreeNode pre;// 前一个节点 private TreeNode first;// 第一个错误节点 private TreeNode second;// 第二个错误节点 public void recoverTree(TreeNode root) {     inorder(root);// 二叉树的中序遍历     // 交换两个节点     int tmp = first.val;     first.val = second.val;     second.val = tmp; } private void inorder(TreeNode cur) {     if (cur == null)         return;     inorder(cur.left);// 递归左子树     // 先找第一个错误节点，如果当前节点比前一个节点值小，说明前一个节点是错误的。     if (first == null && pre != null && cur.val < pre.val)         first = pre;     // 第一个错误节点找到之后再找第二个。     if (first != null && cur.val < pre.val)         second = cur;     pre = cur;// 更新前一个节点     inorder(cur.right);// 递归右子树 }

C++：

private:     TreeNode *pre;// 前一个节点     TreeNode *first;// 第一个错误节点     TreeNode *second;// 第二个错误节点     void inorder(TreeNode *cur) {         if (cur == nullptr)             return;         inorder(cur->left);// 递归左子树         // 先找第一个错误节点，如果当前节点比前一个节点值小，说明前一个节点是错误的。         if (first == nullptr && pre && cur->val < pre->val)             first = pre;         // 第一个错误节点找到之后再找第二个。         if (first && cur->val < pre->val)             second = cur;         pre = cur;// 更新前一个节点         inorder(cur->right);// 递归右子树     } public:     void recoverTree(TreeNode *root) {         inorder(root);// 二叉树的中序遍历         // 交换两个节点的值         int tmp = first->val;         first->val = second->val;         second->val = tmp;     }

Python：

def recoverTree(self, root: Optional[TreeNode]) -> None:     self.pre = None  # 前一个节点     self.first = None  # 第一个错误节点     self.second = None  # 第二个错误节点     def inorder(cur):         if cur is None:             return         inorder(cur.left)  # 递归左子树         # 先找第一个错误节点，如果当前节点比前一个节点值小，说明前一个节点是错误的。         if self.first is None and self.pre is not None and cur.val < self.pre.val:             self.first = self.pre             # 第一个错误节点找到之后再找第二个。         if self.first is not None and cur.val < self.pre.val:             self.second = cur         self.pre = cur  # 更新前一个节点         inorder(cur.right)  # 递归右子树     inorder(root)  # 二叉树的中序遍历     # 交换两个节点     self.first.val, self.second.val = self.second.val, self.first.val

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。