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?
Solution1：In order dfs
思路： 看哪个违反增序，实现时考虑inorder相邻情况
Time Complexity: O(N) Space Complexity: O(N)
Solution2：Morris Traversal
TBC
Time Complexity: O(N) Space Complexity: O(1)
Solution1 Code：
class Solution {
private TreeNode node1, node2;
private TreeNode prev = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
if(root == null) return;
inorderCheck(root);
int tmp = node1.val;
node1.val = node2.val;
node2.val = tmp;
}
private void inorderCheck(TreeNode node) {
if(node == null) return;
inorderCheck(node.left);
// in_order
if(node1 == null && node.val <= prev.val) {
node2 = node;
node1 = prev;
}
else if(node1 != null && node.val <= prev.val) {
node2 = node;
}
prev = node;
inorderCheck(node.right);
}
}
