【Leetcode】Recover Binary Search Tree
來源：程序員人生 發(fā)布時間：2016-06-04 08:46:50 閱讀次數(shù)：2418次
題目鏈接：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.中序 保存所有結(jié)點(diǎn) 空間復(fù)雜度O(n)
2.中序遞歸 保存前1個結(jié)點(diǎn)的指針 找到不對的結(jié)點(diǎn)
算法：
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結(jié)點(diǎn)
first = pre;
second = root;
} else {// 如果第2次逆序 只需要交換first和third結(jié)點(diǎn)
third = root;
}
}
}
pre = root;
inorder(root.right);
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
