LeetCode Recover Binary Search Tree (java)
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?
Java Solution
We can use a stack to do an in order traverse of the tree, as it can produce a sorted list of a binary search tree. In the process, we keep track of two pointers pre, cur:
If we encounter pre.val > cur.val the first time, we get the first error node p1 = pre, and the potential second error node p2 = cur.
If we encounter pre.val > cur.val the second time, we get the second error node p2 = cur.
Finally, we exchange the value of p1 and p2 to recover the binary tree.
|
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 |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public void recoverTree(TreeNode root) { TreeNode p1 = null; TreeNode p2 = null; Stack<TreeNode> s = new Stack<>(); TreeNode p = root; TreeNode pre = null; // 1 2 3 4 5 6 // 1 4 3 2 5 6 while(p!= null || !s.isEmpty()) { if(p != null) { s.push(p); p = p.left; } else { p = s.pop(); if(pre != null && pre.val > p.val) { if(p1 == null) { p1 = pre; p2 = p; } else { p2 = p; break; } } pre = p; p = p.right; } } int tmp = p1.val; p1.val = p2.val; p2.val = tmp; } } |
The above solution uses O(n) space. To get a O(1) space solution, we can use the idea of morris traverse or Threaded binary tree to do an inorder Tree Traversal without recursion and without stack.
See the following code for the O(1) space solution:
|
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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public void recoverTree(TreeNode root) { TreeNode p1 = null; TreeNode p2 = null; TreeNode cur = root; TreeNode pre = null; // 1 2 3 4 5 6 // 1 4 3 2 5 6 while(cur!= null ) { if(cur.left == null) { if(pre!= null ) { if(pre.val > cur.val) { if (p1 == null){ p1 = pre; } p2 = cur; } } pre = cur; cur = cur.right; } else{ // get the pre node of p TreeNode preNode = cur.left; while(preNode.right != null && preNode.right != cur) { preNode = preNode.right; } //set up preNode, traverser left sub tree if(preNode.right == null){ preNode.right = cur; cur = cur.left; } else { preNode.right = null; if(pre!= null ) { if(pre.val >= cur.val) { if (p1 == null){ p1 = pre; } p2 = cur; } } pre = cur; cur = cur.right; } } } int tmp = p1.val; p1.val = p2.val; p2.val = tmp; } } |
