Recover Binary Search Tree
Sep 1 '12
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?
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
public class Solution { ArrayList<TreeNode> nodes; ArrayList<Integer> values; public void recoverTree(TreeNode root) { // Start typing your Java solution below // DO NOT write main() function nodes = new ArrayList<TreeNode>(); values= new ArrayList<Integer>(); inorder(root); Collections.sort(values); int index = 0; for(TreeNode n:nodes){ n.val = values.get(index++); } } public void inorder(TreeNode root){ if(root == null) return; inorder(root.left); nodes.add(root); values.add(root.val) ; inorder(root.right); } }
public class Solution { public void recoverTree(TreeNode root) { // Start typing your Java solution below // DO NOT write main() function ArrayList<TreeNode> nodes = new ArrayList<TreeNode>(); inOrderTraverse(root, nodes); int i, j; for( i =0; nodes.get(i).val<nodes.get(i+1).val; i++); for( j =nodes.size()-1; nodes.get(j).val>nodes.get(j-1).val; j--); int temp = nodes.get(i).val; nodes.get(i).val = nodes.get(j).val; nodes.get(j).val = temp; return; } public void inOrderTraverse(TreeNode node, ArrayList<TreeNode> nodes){ if(node == null) return; inOrderTraverse(node.left, nodes); nodes.add(node); inOrderTraverse(node.right, nodes); } }