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?
Solution 1: in order traversal, use stack though, but at the end stack is empty. Below is iterative way, recursive is simpler but use system stack, same thing. A real O(1) need Morris Traversal.
public class Solution {
public void recoverTree(TreeNode root) {
Deque<TreeNode> stack=new LinkedList<>();
TreeNode p1=null, p2=null, pre=null, x=root;
while (x!=null || !stack.isEmpty()) {
if (x!=null) {
stack.push(x);
x=x.left;
}
else {
x=stack.pop();
if (pre!=null && pre.val>x.val) {
if (p1==null) {
p1=pre;
p2=x;// incase in sorted array p1,p2 is next to each other
}
else p2=x;
}
pre=x;
x=x.right;
}
}
int temp=p1.val;
p1.val=p2.val;
p2.val=temp;
}
}
没有评论:
发表评论