题目:
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下,恢复这棵树。
输入: [1,3,null,null,2]
1
/
3
\
2
输出: [3,1,null,null,2]
3
/
1
\
2
输入: [3,1,4,null,null,2]
3
/ \
1 4
/
2
输出: [2,1,4,null,null,3]
2
/ \
1 4
/
3
抛砖引玉
思路
二叉搜索树(二叉查找树,二叉排序树):
中序遍历
中序遍历二叉搜索树得到节点应该是递增的,存在位置错误则一定存在非递增节点
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var recoverTree = function (root) {
let nums = []
inorder(root, nums)
let [first, second] = findTwoSwapped(nums)
// 默认替换两个节点,如只需替换一个传入的替换元素为-1,则查找不到
recover(root, 2, first, second)
// 中序遍历
function inorder(root, nums) {
if (root === null) return
// 先遍历左节点
inorder(root.left, nums)
// 再遍历根节点
nums.push(root.val)
// 最后遍历有节点
inorder(root.right, nums)
}
// 循环中序遍历得到的节点,查找非递增节点
function findTwoSwapped(nums) {
const n = nums.length
let x = -1,
y = -1
for (let i = 0; i < n - 1; ++i) {
// 存在非递增节点,则返回
if (nums[i + 1] < nums[i]) {
y = nums[i + 1]
if (x === -1) {
x = nums[i]
} else {
// 找到两个节点终止查找
break
}
}
}
return [x, y]
}
// 遍历二叉树替换查找的非递增节点
function recover(node, count, x, y) {
if (node !== null) {
if (node.val === x || node.val === y) {
node.val = node.val === x ? y : x
if (--count === 0) return
recover(node.left, count, x, y)
recover(node.right, count, x, y)
}
}
}
}
var recoverTree = function (root) {
let stack = [],
x = null,
y = null,
pred = null
// 隐式中序遍历
while (stack.length || root !== null) {
// 先循环左节点
while (root !== null) {
stack.push(root)
root = root.left
}
// 取出最后一个节点与上一个节点比较 a vs [....←]
root = stack.pop()
// 存在非递增节点,则存放到x,y中
if (pred !== null && root.val < pred.val) {
y = root
if (x === null) {
x = pred
} else {
// 找到两个节点终止查找
break
}
}
// 本轮最后一个节点存放到上一个节点位置
pred = root
// 在循环右侧节点
root = root.right
}
swap(x, y)
// 交换节点
function swap(x, y) {
const temp = x.val
x.val = y.val
y.val = temp
}
}
查找当前节点的前一个节点 node
var recoverTree = function (root) {
let x = null,
y = null,
pred = null,
node = null
while (root !== null) {
// 假设当前节点为根节点,找到中序遍历时他的前一个节点
// 存在左子树则前一个节点应该在其左子树上的最右叶子节点
if (root.left !== null) {
node = root.left
// 找当前二叉树左子树的最后一个叶子节点
while (node.right !== null && node.right !== root) {
node = node.right
}
if (node.right === null) {
// 拼接上衔接该整改左子树的上一个节点
node.right = root
// 拼接上来节点就成了下一个'当前节点',其就是下一个需要遍历的对象,对其执行同样的操作
root = root.left
} else {
// '当前节点'不存在左子树遍历完成,则这个节点就是上一个根节点的前一个节点
// 比较他们的大小查看是否满足递增,如果不是则需要替换他们
if (pred !== null && root.val < pred.val) {
y = root
if (x === null) {
x = pred
}
}
// 记录当前节点上一个节点
pred = root
// 复原指向
node.right = null
root = root.right
}
} else {
// 如果没有左子树,则在右子树中遇到当前节点的中序遍历的前一个叶子节点
// 比较他们的大小查看是否满足递增,如果不是则需要替换他们
if (pred !== null && root.val < pred.val) {
y = root
if (x === null) {
x = pred
}
}
// 记录当前节点上一个节点
pred = root
// 复原指向
root = root.right
}
}
swap(x, y)
// 交换节点
function swap(x, y) {
const temp = x.val
x.val = y.val
y.val = temp
}
}