LeetCode: Recover Binary Search Tree

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?

Solution One

Key Point: 1. the sequence of values should be in the ascending order with in-order traversal
2. The previous node should be held
3. It's not really O(1) space since the recursion stack needs O(n) extra space

	void recoverTree(TreeNode *root) {
	TreeNode *first=NULL;
	TreeNode *second=NULL;
	TreeNode *prev=NULL;
	if(root==NULL) return;
	recoverTreeRe(root, prev, first, second);
	if(first && second)
	std::swap(first->val, second->val);
	}
	void recoverTreeRe(TreeNode *root, TreeNode *&preNode, TreeNode* &first, TreeNode* &second){
	if(root==NULL) return;
	recoverTreeRe(root->left, preNode, first, second);
	if(preNode && root->val < preNode->val){
	//very careful, might be (0,1), swap two consecutive elements(in order traversal)
	/* if(!first)
	first = preNode;
	else
	second = root;*/
	second = root;
	if(!first)
	first = preNode;
	}
	preNode = root;//this statement is essential
	recoverTreeRe(root->right, preNode, first, second);
	}

view raw gistfile1.cpp hosted with ❤ by GitHub

Solution Two

I implemented it in Java with O(N) space. Using two ArrayLists to hold the sequence of nodes and values.

	public void recoverTree(TreeNode root) {
	ArrayList<TreeNode> nodeList = new ArrayList<TreeNode>();
	ArrayList<Integer> valList = new ArrayList<Integer>();
	if(root==null) return;
	recoverTreeRe(root, nodeList, valList);
	int first=-1, second = -1;
	for(int i=1; i<valList.size(); i++){
	if(valList.get(i)<valList.get(i-1)){
	second = i;
	if(first == -1)
	first = i-1;
	}
	}
	int temp = nodeList.get(first).val;
	nodeList.get(first).val = nodeList.get(second).val;
	nodeList.get(second).val = temp;
	}
	void recoverTreeRe(TreeNode root, ArrayList<TreeNode> nodeList, ArrayList<Integer> valList){
	if(root==null) return;
	recoverTreeRe(root.left, nodeList, valList);
	nodeList.add(root);
	valList.add(root.val);
	recoverTreeRe(root.right, nodeList, valList);
	}

view raw gistfile1.java hosted with ❤ by GitHub