99、恢复二叉搜索树
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 1:
输入: [1,3,null,null,2]
1
/
3
\
2
输出: [3,1,null,null,2]
3
/
1
\
2
示例 2:
输入: [3,1,4,null,null,2]
3
/ \
1 4
/
2
输出: [2,1,4,null,null,3]
2
/ \
1 4
/
3
进阶:
- 使用 O(n) 空间复杂度的解法很容易实现。
- 你能想出一个只使用常数空间的解决方案吗？
链接：https://leetcode-cn.com/problems/recover-binary-search-tree
题解
1、利用中序遍历的有序性
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void recoverTree(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>();
TreeNode firstNode = null;
TreeNode secondNode = null;
// 记录前一个结点
TreeNode pre = new TreeNode(Integer.MIN_VALUE);
TreeNode p = root;
while (p != null || !stack.isEmpty()) {
while (p != null) {
stack.push(p);
p = p.left;
}
p = stack.pop();
if (firstNode == null && pre.val > p.val) firstNode = pre;
if (firstNode != null && pre.val > p.val) secondNode = p;
pre = p;
p = p.right;
}
// 恢复两个结点的位置
int tmp = firstNode.val;
firstNode.val = secondNode.val;
secondNode.val = tmp;
}
}
// 作者：powcai
// 链接：https://leetcode-cn.com/problems/recover-binary-search-tree/solution/zhong-xu-bian-li-by-powcai/
- 递归版
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode firstNode = null;
TreeNode secondNode = null;
TreeNode preNode = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
in_order(root);
int tmp = firstNode.val;
firstNode.val = secondNode.val;
secondNode.val = tmp;
}
private void in_order(TreeNode root) {
if (root == null) return;
in_order(root.left);
if (firstNode == null && preNode.val > root.val) firstNode = preNode;
if (firstNode != null && preNode.val > root.val) secondNode = root;
preNode = root;
in_order(root.right);
}
}
// 作者：powcai
// 链接：https://leetcode-cn.com/problems/recover-binary-search-tree/solution/zhong-xu-bian-li-by-powcai/
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
