99. Recover Binary Search Tree
99. Recover Binary Search Tree
🟠 🔖 树
深度优先搜索
二叉搜索树
二叉树
🔗 LeetCode
题目
You are given the root
of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
Example 1:
![](https://assets.leetcode.com/uploads/2020/10/28/recover1.jpg)
Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.
Example 2:
![](https://assets.leetcode.com/uploads/2020/10/28/recover2.jpg)
Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.
Constraints:
- The number of nodes in the tree is in the range
[2, 1000]
. -2^31 <= Node.val <= 2^31 - 1
Follow up: A solution using O(n)
space is pretty straight-forward. Could you devise a constant O(1)
space solution?
题目大意
给你二叉搜索树的根节点 root
,该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下,恢复这棵树 。
解题思路
根据 BST 的性质,BST 的中序遍历是升序的,我们可以通过中序遍历来找到这两个错误节点,并交换它们的值,从而恢复 BST 的正确顺序。
- 进行 BST 的中序遍历,并记录先前访问的节点
prev
; - 在遍历过程中,如果发现当前节点的值小于先前节点的值,说明找到了一个错误节点;
- 记录这两个错误节点,并继续遍历;
- 遍历结束后,交换这两个错误节点的值,即完成修复操作;
代码
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var recoverTree = function (root) {
let prev = null;
let first = null;
let second = null;
const traverse = (root) => {
if (!root) return;
traverse(root.left);
if (prev != null && prev.val >= root.val) {
if (first == null) {
first = prev;
}
second = root;
}
prev = root;
traverse(root.right);
};
traverse(root);
const temp = first.val;
first.val = second.val;
second.val = temp;
};