字节五面
今天脉脉看到一篇帖子：
楼主是 tx 的前员工，在字节五面（加轮）被挂后，认定（或许私下做了一些调查）是字节 HR 向 tx 背调，然后被前同事捏造虚假信息，导致的面试失利。
看完这帖子，我第一反应是：不至于吧？有没有可能是脑补情节大于实际？
于是我搜索了一下「字节五面」关键字，看到了以下的内容：
似乎「字节五面挂」已经是一个普遍现象，光集中出现在 2023-11 时间段的就不少，更何况实际中可能还有"沉默的大多数"。
相比于最开始帖子的阴谋论，或许「五面挂」和「字节刷 KPI」的关联性更大一些。
这确实很难受，毕竟已经到五面了，对双方来说都是巨大的沉没成本，如果求职者是处于离职状态的话，伤害则更大。
对于这种情况，可以引用回之前 阿里员工面试 PDD 四面通过，但最终还是被挂 的建议：
""
确实，有时候我们很难判断 HR 是真的缺乏专业性，还是因为不想招人了而进行的故意拖延。
但我们又无法要求将 HR 沟通的这一步进行前置，这不现实。
目前所能做的最合理的做法只能是：求职过程中，有些公司的流程快，有些公司流程慢，无论快慢，都以发 offer 为准，不要将流程的繁琐视为沉没成本，如果在已经离职的情况下，尽量多家面试并行投递推进，既可以帮助自己快速进入面试状态，也不会落入流程走了一个多月，到之后没谈拢的局面。
""
...
回归主题。
来一道和「字节跳动」相关的算法原题。
题目描述
平台：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 使二叉搜索树有效。
提示：
-
树上节点的数目在范围 内 -
进阶：使用 空间复杂度的解法很容易实现。你能想出一个只使用 空间的解决方案吗？
基本分析
首先，别想复杂了。
所谓的恢复二叉树（两节点互换），只需要将两节点的 val 进行互换即可，而不需要对节点本身进行互换。
中序遍历 - 递归 & 迭代
二叉搜索树，其中序遍历是有序的。
要找到哪两个节点被互换，可通过比对中序遍历序列来实现。
但将整个中序遍历序列保存下来，再检测序列有序性的做法，复杂度是 的（不要说题目要求的 ，连 都达不到）。
所以第一步，「这个「递归 & 迭代」的次优解，我们先考虑如何做到 的空间复杂度，即在中序遍历过程中找到互换节点」。
其实也很简单，除了使用 a 和 b 来记录互换节点，额外使用变量 last 来记录当前遍历过程中的前一节点即可：
若存在前一节点 last 存在，而且满足前一节点值大于当前节点（last.val > root.val），违反“有序性”，根据是否为首次出现该情况分情况讨论：
-
若是首次满足条件，即
a == null，此时上一节点last必然是两个互换节点之一，而当前root只能说是待定，因为有可能是last和root实现互换，也有可能是last和后续的某个节点实现互换。此时有
a = last, b = root -
若是非首次满足条件，即
a != null，此时当前节点root必然是两个互换节点中的另外一个。此时有
b = root
综上：如果整个中序遍历的序列中“逆序对”为一对，那么互换节点为该“逆序对”的两个成员；若“逆序对”数量为两对，则互换节点为「第一对“逆序对”的首个节点」和「第二对“逆序对”的第二个节点」。
Java 代码（递归）：
class Solution {
TreeNode a = null, b = null, last = null;
public void recoverTree(TreeNode root) {
dfs(root);
int val = a.val;
a.val = b.val;
b.val = val;
}
void dfs(TreeNode root) {
if (root == null) return ;
dfs(root.left);
if (last != null && last.val > root.val) {
if (a == null) {
a = last; b = root;
} else {
b = root;
}
}
last = root;
dfs(root.right);
}
}
Java 代码（迭代）：
class Solution {
public void recoverTree(TreeNode root) {
Deque<TreeNode> d = new ArrayDeque<>();
TreeNode a = null, b = null, last = null;
while (root != null || !d.isEmpty()) {
while (root != null) {
d.addLast(root);
root = root.left;
}
root = d.pollLast();
if (last != null && last.val > root.val) {
if (a == null) {
a = last; b = root;
} else {
b = root;
}
}
last = root;
root = root.right;
}
int val = a.val;
a.val = b.val;
b.val = val;
}
}
-
时间复杂度： -
空间复杂度： ，其中 为树高
中序遍历 - Morris 遍历
Morris 遍历也就是经常说到的“神级遍历”，其本质是通过做大常数来降低空间复杂度。
还是以二叉树的中序遍历为例，无论是递归或是迭代，为了在遍历完左节点（也可以是左子树）时，仍能回到父节点，我们需要使用数据结构栈，只不过在递归做法中是用函数调用充当栈，而在迭代做法则是显式栈。
「这使得空间复杂度为 ，而 Morris 遍历的核心则是利用“路径底部节点”中的空闲指针进行线索。」
举个 🌰，对于一棵最简单的二叉树：
在中序遍历过程中，如果选择递归或迭代方式，并且不使用栈的情况，当遍历完左子节点（或左子树的最后一个节点）后，将会面临无法返回根节点的问题。
在 Morris 遍历中，从根节点开始，尚未真正遍历左子节点之前，就会先建立「左子节点（或左子树的最后一个节点）」与「当前根节点」之间的链接，从而避免使用栈。
具体的，Morris 遍历的中序遍历遵循如下流程（喜欢的话可以背过）：
-
令根节点为当前节点
-
只要当前节点不为空（
while (root != null)），重复执行如下流程：-
若当前节点的左子节点为空（
root.left = null），将当前节点更新为其右子节点（root = root.right) -
若当前节点的左子节点不为空，利用临时变量
t存储，找到当前节点的前驱节点（左子树中最后一个节点）：-
若前驱节点的右子节点为空（ t.right = null），将前驱节点的右子节点链接到当前节点（t.right = root），并将当前节点更新为左子节点（root = root.left） -
若前驱节点的右子节点不为空，说明已链接到当前节点，此时将前驱节点的右子节点置空（删除链接 t.right = null），遍历当前节点，并将当前节点更新为右子节点（root = root.right）
-
-
Java 代码：
class Solution {
public void recoverTree(TreeNode root) {
TreeNode a = null, b = null, last = null;
while (root != null) {
if (root.left == null) {
if (last != null && last.val > root.val) {
if (a == null) {
a = last; b = root;
} else {
b = root;
}
}
last = root;
root = root.right;
} else {
TreeNode t = root.left;
while (t.right != null && t.right != root) t = t.right;
if (t.right == null) { // 若前驱节点右子树为空, 说明是真正遍历左子树前, 建立与当前根节点的链接, 然后开始真正遍历左子树
t.right = root;
root = root.left;
} else { // 若已存在链接, 说明是第二次访问根节点, 左子树（前驱节点）已遍历完, 此时应该解开链接, 遍历当前节点以及右子树
t.right = null;
if (last != null && last.val > root.val) {
if (a == null) {
a = last; b = root;
} else {
b = root;
}
}
last = root;
root = root.right;
}
}
}
int val = a.val;
a.val = b.val;
b.val = val;
}
}
C++ 代码：
class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode *a = nullptr, *b = nullptr, *last = nullptr;
while (root != nullptr) {
if (root->left == nullptr) {
if (last != nullptr && last->val > root->val) {
if (a == nullptr) {
a = last; b = root;
} else {
b = root;
}
}
last = root;
root = root->right;
} else {
TreeNode *t = root->left;
while (t->right != nullptr && t->right != root) t = t->right;
if (t->right == nullptr) {
t->right = root;
root = root->left;
} else {
t->right = nullptr;
if (last != nullptr && last->val > root->val) {
if (a == nullptr) {
a = last, b = root;
} else {
b = root;
}
}
last = root;
root = root->right;
}
}
}
swap(a->val, b->val);
}
};
-
时间复杂度： -
空间复杂度：
最后
给大伙通知一下 📢 ：
全网最低价 LeetCode 会员目前仍可用！！！
📅 年度会员：有效期加赠两个月！！; 季度会员：有效期加赠两周！！
🧧 年度会员：获 66.66 现金红包！！; 季度会员：获 22.22 现金红包！！
🎁 年度会员：参与当月丰厚专属实物抽奖（中奖率 > 30%)！！
专属链接：leetcode.cn/premium/?promoChannel=acoier
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
