恢复二叉搜索树
解题思路：
-
中序遍历BST，依次访问的节点值是递增的，错误的BST会破坏递增性，从而能定位出错误，错误有两种：
- 错误1：出现了两对不满足前小后大，需要交换第一对的第一个元素与第二对的第二个元素；
- 错误2：只出现一对不满足前小后大，交换这一对元素即可；
![]( "恢复二叉搜索树")
-
比较前后访问的节点值，prev 保存上一个访问的节点（中序遍历是递增的，所以上一个节点永远小于当前节点），当前访问的是 root 节点；
- 每访问一个节点，如果 prev.val>=root.val，就找到了一对“错误对”；
- 检查一下它是第一对错误对，还是第二对错误对；
-
遍历结束，就确定了待交换的两个错误点，进行交换；
复杂度：
-
时间复杂度：O(n)，n 是节点个数；
-
空间复杂度：O(n)，递归栈的深度；
代码实现：
const recoverTree = (root) => {
// 上一个访问的节点
let perv = new TreeNode(-Infinity);
// 错误节点
let err1, err2 = null;
// 中序递归遍历
const inOrder = (root) => {
if (root == null) {
return;
}
inOrder(root.left);
if (perv.val >= root.val && err1 == null) { // 当前是第一对错误
err1 = perv; // 记录第一个错误点
}
if (perv.val >= root.val && err1 != null) { // 第一个错误点已确定
err2 = root; // 记录第二个错误点
}
perv = root; // 更新 perv
inOrder(root.right);
};
inOrder(root);
// 交换两个错误位置的节点
[err1.val, err2.val] = [err2.val, err1.val];
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
1346.检查整数及其两倍数是否存在
上一篇
评论
