多位95后程序员获公司700万大奖。。。

在百度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 使二叉搜索树有效。

问题分析

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

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

比如正常二叉搜索树中遍历的结果是:[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