一、题目描述:
给你二叉搜索树的根节点 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 使二叉搜索树有效。
提示:
树上节点的数目在范围 [2, 1000] 内
-231 <= Node.val <= 231 - 1
进阶:使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗?
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/recover-binary-search-tree
二、思路分析:
一个合格的二叉搜索树的中序遍历一定是个严格递增的序列,如果发生了交换,可能会有两种情况:
交换的是相邻的节点,即发现一个节点值小于其前一个节点值时,这两个节点就刚好是被交换的。
交换的是不相邻的节点,即发现了两次异常,第一次是:A节点值大于其后一个节点值,第二次是:B节点值小于其前一个节点值。A和B就是被交换的两个节点。
首先,二叉搜索树的中序遍历出的节点是有序的
其次,并没有说交换的节点是相邻的,所以不能直接交换 pre->val 与 root->val
所以我们要找到两个不符合前一个节点值小于后一个节点值的点。
最后,将两节点交换。
过程:第一次找到(前大后小),由于x == nullptr,所以x = pre,之后的遍历都不会再对x产生影响,
只会改变y的值。
三、AC 代码:
class Solution {
public void recoverTree(TreeNode root) {
Deque<TreeNode> stk = new ArrayDeque<>();
TreeNode x = null, y = null, pre = null;
while (root != null || !stk.isEmpty()) {
while (root != null) {
stk.offer(root);
root = root.left;
}
root = stk.pollLast();
if (pre != null && pre.val > root.val) {
y = root;
if (x == null) {
x = pre;
} else {
break;
}
}
pre = root;
root = root.right;
}
// 交换节点
int tmp = x.val;
x.val = y.val;
y.val = tmp;
}
}
四、总结:
掘友们,解题不易,留下个赞或评论再走吧!谢啦~ 💐
希望对你有帮助
期待下次再见~
🌇 点赞 👍 收藏 ⭐留言 📝 一键三连 ~关注Jam,从你我做起!