【Leetcode】Recover Binary Search Tree
来源：程序员人生 发布时间：2016-06-04 08:46:50 阅读次数：2046次
题目链接：https://leetcode.com/problems/recover-binary-search-tree/
题目：
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n)
space is pretty straight forward. Could you devise a constant space solution?
思路：
1.中序 保存所有结点 空间复杂度O(n)
2.中序递归 保存前1个结点的指针 找到不对的结点
算法：
public void recoverTree(TreeNode root) {
inorder(root);
if (third != null) {// 2次逆序
int tmp = first.val;
first.val = third.val;
third.val = tmp;
} else {// 1次逆序
int tmp = second.val;
second.val = first.val;
first.val = tmp;
}
}
TreeNode pre, first, second, third;
public void inorder(TreeNode root) {
if (root == null)
return;
inorder(root.left);
if (pre == null) {
pre = root;
} else {
if (root.val < pre.val) {
if (first == null) { // 如果第1次逆序 需要交换first和second结点
first = pre;
second = root;
} else {// 如果第2次逆序 只需要交换first和third结点
third = root;
}
}
}
pre = root;
inorder(root.right);
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
