在百度9月19日內部活動上，李彥宏為激勵員工的創新與研發精神，給4支內部團隊頒發「百度最高獎」，每支團隊獲獎100萬美元(合700萬人民幣)，總額超2800萬人民幣，獲獎團隊中有多位95後成員。
在活動上，李彥宏說：「不是說，公司比較順的時候，我們多發幾個獎，逆境的時候，我們就少發幾個獎， 我們再苦不能苦技術人員 ，百度的技術信仰是一貫的 ，是永遠的。」
--------------下面是今天的演算法題--------------
來看下今天的演算法題，這題是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;// 第二個錯誤節點
publicvoidrecoverTree(TreeNode root){
inorder(root);// 二元樹的中序遍歷
// 交換兩個節點
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
privatevoidinorder(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;// 第二個錯誤節點
voidinorder(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:
voidrecoverTree(TreeNode *root){
inorder(root);// 二元樹的中序遍歷
// 交換兩個節點的值
int tmp = first->val;
first->val = second->val;
second->val = tmp;
}
Python：
defrecoverTree(self, root: Optional[TreeNode]) -> None:
self.pre = None# 前一個節點
self.first = None# 第一個錯誤節點
self.second = None# 第二個錯誤節點
definorder(cur):
if cur isNone:
return
inorder(cur.left) # 遞迴左子樹
# 先找第一個錯誤節點，如果當前節點比前一個節點值小，說明前一個節點是錯誤的。
if self.first isNoneand self.pre isnotNoneand cur.val < self.pre.val:
self.first = self.pre
# 第一個錯誤節點找到之後再找第二個。
if self.first isnotNoneand 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
