專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

最近文心一言宣布4月1日免費了，這確實是一個好消息，雖然百度的產(chǎn)品負面評價比較多，主要是百度搜索時候的廣告和網(wǎng)盤限速，但百度在搜索這塊的技術(shù)還是有的。

百度太急功近利了，AI大模型一出來的時候就想收費，我常用的AI搜索有Kimi，文心一言，騰訊元寶，豆包，訊飛星火，通義千問，天工超能……有十幾個，目前也只有文心一言敢收費。目前文心一言4.0還是收費的，只有3.5是免費的。之前想充值體驗一下的，這次正好免費了，到時候看下效果怎么樣？不過我覺得這次免費應(yīng)該是受DeepSeek的影響，文心一言再不免費，估計用戶要全部流失了。

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

來看下今天的算法題，這題是LeetCode的第99題：恢復(fù)二叉搜索樹。

問題描述

來源：LeetCode第99題

難度：中等

給你二叉搜索樹的根節(jié)點 root ，該樹中的 恰好兩個節(jié)點的值被錯誤地交換 。請在不改變其結(jié)構(gòu)的情況下，恢復(fù)這棵樹 。

示例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 使二叉搜索樹有效。

• 樹上節(jié)點的數(shù)目在范圍 [2, 1000] 內(nèi)

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

問題分析

這題說的是一顆二叉搜索樹的兩個節(jié)點被錯誤的交換，讓我們恢復(fù)這棵二叉搜索樹。

我們知道 二叉搜索樹的中序遍歷結(jié)果是有序的 ，我們只需要對這棵二叉搜索樹進行中序遍歷，就可以找出這兩個錯誤的節(jié)點，最后交換它們的值即可。

比如正常二叉搜索樹中遍歷的結(jié)果是:[1,2,3,4,5]，是有序的，由于錯誤交換兩個節(jié)點，比如2和4交換，導(dǎo)致中序遍歷的結(jié)果變成[1,4,3,2,5]，在中序遍歷的時候每次都會和前一個節(jié)點值比較，如果當(dāng)前節(jié)點比前一個節(jié)點值小，說明出現(xiàn)了錯誤的節(jié)點。

比如第一次3比4小，說明4(pre)是第一個錯誤節(jié)點，第二次是2比3小，說明2(cur)是第二個錯誤節(jié)點，最后交換它們的值即可。

JAVA：

private TreeNode pre;// 前一個節(jié)點 private TreeNode first;// 第一個錯誤節(jié)點 private TreeNode second;// 第二個錯誤節(jié)點 public void recoverTree(TreeNode root) {     inorder(root);// 二叉樹的中序遍歷     // 交換兩個節(jié)點     int tmp = first.val;     first.val = second.val;     second.val = tmp; } private void inorder(TreeNode cur) {     if (cur == null)         return;     inorder(cur.left);// 遞歸左子樹     // 先找第一個錯誤節(jié)點，如果當(dāng)前節(jié)點比前一個節(jié)點值小，說明前一個節(jié)點是錯誤的。     if (first == null && pre != null && cur.val < pre.val)         first = pre;     // 第一個錯誤節(jié)點找到之后再找第二個。     if (first != null && cur.val < pre.val)         second = cur;     pre = cur;// 更新前一個節(jié)點     inorder(cur.right);// 遞歸右子樹 }

C++：

private:     TreeNode *pre;// 前一個節(jié)點     TreeNode *first;// 第一個錯誤節(jié)點     TreeNode *second;// 第二個錯誤節(jié)點     void inorder(TreeNode *cur) {         if (cur == nullptr)             return;         inorder(cur->left);// 遞歸左子樹         // 先找第一個錯誤節(jié)點，如果當(dāng)前節(jié)點比前一個節(jié)點值小，說明前一個節(jié)點是錯誤的。         if (first == nullptr && pre && cur->val < pre->val)             first = pre;         // 第一個錯誤節(jié)點找到之后再找第二個。         if (first && cur->val < pre->val)             second = cur;         pre = cur;// 更新前一個節(jié)點         inorder(cur->right);// 遞歸右子樹     } public:     void recoverTree(TreeNode *root) {         inorder(root);// 二叉樹的中序遍歷         // 交換兩個節(jié)點的值         int tmp = first->val;         first->val = second->val;         second->val = tmp;     }

Python：

def recoverTree(self, root: Optional[TreeNode]) -> None:     self.pre = None  # 前一個節(jié)點     self.first = None  # 第一個錯誤節(jié)點     self.second = None  # 第二個錯誤節(jié)點     def inorder(cur):         if cur is None:             return         inorder(cur.left)  # 遞歸左子樹         # 先找第一個錯誤節(jié)點，如果當(dāng)前節(jié)點比前一個節(jié)點值小，說明前一個節(jié)點是錯誤的。         if self.first is None and self.pre is not None and cur.val < self.pre.val:             self.first = self.pre             # 第一個錯誤節(jié)點找到之后再找第二個。         if self.first is not None and cur.val < self.pre.val:             self.second = cur         self.pre = cur  # 更新前一個節(jié)點         inorder(cur.right)  # 遞歸右子樹     inorder(root)  # 二叉樹的中序遍歷     # 交換兩個節(jié)點     self.first.val, self.second.val = self.second.val, self.first.val

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。