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?
Analysis
We can use in-order traverse to find the swapped element. During the traverse, we can find the element that is smaller than the previous node. Using this method we can find the swapped node. Save it and swap them. Done.
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
public class Solution { TreeNode node1 = null; TreeNode node2 = null; public void recoverTree(TreeNode root) { inorderTraverse(root); int tmp = node1.val; node1.val = node2.val; node2.val = tmp; } TreeNode prev = null; private void inorderTraverse(TreeNode root) { if (root == null) return; inorderTraverse(root.left); if (prev != null) { if (root.val <= prev.val) { if (node1 == null) node1 = prev; node2 = root; } } prev = root; inorderTraverse(root.right); } } |
Complexity
The time complexity is $O(n)$. But the space complexity is not constant, since we use recursive function.
Follow-up
After searching, I found there is a way to use $O(1)$ space to do the in-order traverse, which is called Morris traverse.
The Morris traverse is like the following.
Firstly, take the root node as current node.
Then there are two possibilities.
- If current node doesn’t have left child, output the value. And current = current.right.
- If current node has left child, try to find the precursor node of current node, which is the right-most node of the left child of current. If the right child of it is null (If we don’t modify the tree, it should be null), set current as its right child, and current = current.left. Otherwise (It means that we have modify the tree and we have traverse all nodes in the left subtree of current node), set it to null, output current. And current = current.right.
During the traverse, we can find the nodes which are needed to be swapped.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
public class Solution { public void recoverTree(TreeNode root) { TreeNode current = root; TreeNode prev = null; TreeNode node1 = null; TreeNode node2 = null; while (current != null) { if (current.left == null) { if (prev != null) { if (prev.val >= current.val) { if (node1 == null) node1 = prev; node2 = current; } } prev = current; current = current.right; } else { TreeNode t = current.left; while (t.right != null && t.right != current) t = t.right; if (t.right == null) { t.right = current; current = current.left; } else { t.right = null; if (prev != null) { if (prev.val >= current.val) { if (node1 == null) node1 = prev; node2 = current; } } prev = current; current = current.right; } } } int tmp = node1.val; node1.val = node2.val; node2.val = tmp; } } |
The space complexity of this algorithm is $O(1)$.
But what about the time complexity? In fact, we only visit every edge twice. One is for going to that node, and another one is for searching the precursor node. There are only $n-1$ edges in a tree. So the time complexity is also $O(n)$.
The Morris traverse can also be used in pre-order and post-order traverse. There is a great article, including the detail pictures. You can visit http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html if you are interested.