Recover Binary Search Tree

LeetCode

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.

Solution: 

Use an extra class called Pre_first_second, which is used to record the previous node of current root node, first wrong node and second wrong node, preoder-traverse the entire tree find the invalid two nodes and store hem into pre-first_sercond structure. 

	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?
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	// 1/31/2014 rewrite version
	class Pre_First_Second{
	TreeNode pre=null;
	TreeNode first=null;
	TreeNode second=null;
	}
	public class Solution {
	public void recoverTree(TreeNode root) {
	if (root==null){
	return;
	}
	Pre_First_Second pfs=new Pre_First_Second();
	findBadPoints(root, pfs);
	int temp=pfs.second.val;
	pfs.second.val=pfs.first.val;
	pfs.first.val=temp;
	}
	private void findBadPoints(TreeNode root, Pre_First_Second pfs){
	if (root==null){
	return;
	}
	findBadPoints(root.left, pfs);
	if (pfs.pre!=null&& pfs.pre.val>root.val){
	if (pfs.first==null){
	pfs.first=pfs.pre;
	}
	pfs.second=root;
	}
	pfs.pre=root;
	findBadPoints(root.right, pfs);
	}
	}
	// below is old version
	class Pre_first_second{
	TreeNode first=null;
	TreeNode second=null;
	TreeNode pre=null;
	}
	public class Solution {
	public void recoverTree(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	// ArrayList<TreeNode>pre_first_second=new ArrayList<TreeNode>(3);
	Pre_first_second pre_first_second=new Pre_first_second();
	inorder(root,pre_first_second);
	TreeNode mistakeNode1=pre_first_second.first;
	TreeNode mistakeNode2=pre_first_second.second;
	int temp=mistakeNode1.val;
	mistakeNode1.val=mistakeNode2.val;
	mistakeNode2.val=temp;
	}
	public void inorder(TreeNode root, Pre_first_second pre_first_second){
	if (root==null){
	return;
	}
	inorder(root.left, pre_first_second);
	if (pre_first_second.pre==null){
	pre_first_second.pre=root;
	}
	else{
	if (pre_first_second.pre.val>root.val){
	if(pre_first_second.first==null){
	pre_first_second.first=pre_first_second.pre;
	}
	pre_first_second.second=root;
	}
	pre_first_second.pre=root;
	}
	inorder(root.right,pre_first_second);
	}
	}

view raw Recover Binary Search Tree.java hosted with ❤ by GitHub