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?

	package leetcode.tree;
	/**
	* Thought: Use inorder traversal --> make it as a increasing array, so the problem convert to find two swap points
	* in a increasing array.
	*
	* 1 2 3 4 5 6 --> 1 5 3 4 2 6 in right array, lastNode.val < root.val should always be true
	* lastNode.val > root.val means there's bad points location there, 1st, lastNode. 2nd, root.
	* 5 5
	* 2 7 7 2 7 > 5 > 2 because we use inorder, so lastNode.val > root.val. --> bad point. 1.lastNode 2.root
	* Don't forget move forward lastNode!
	*
	* In addition, o(n) solution. inOrderTraversal and reassign values.
	*
	* @author jeffwan
	* @date Feb 13, 2014
	*/
	public class RecoverTree {
	private TreeNode firstNode = null;
	private TreeNode secondNode = null;
	private TreeNode lastNode = new TreeNode(Integer.MIN_VALUE);
	public void recoverTree(TreeNode root) {
	// Find out two bad points
	traversal(root);
	// Swap value of two points
	int temp = firstNode.val;
	firstNode.val = secondNode.val;
	secondNode.val = temp;
	}
	private void traversal(TreeNode root) {
	if (root == null) {
	return;
	}
	traversal(root.left);
	if (firstNode == null && lastNode.val > root.val) {
	firstNode = lastNode;
	}
	if (firstNode != null && lastNode.val > root.val) {
	secondNode = root;
	}
	lastNode = root;
	traversal(root.right);
	}
	// TreeNode
	public class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw RecoverTree.java hosted with ❤ by GitHub