Leetcode Recover Binary Search Tree

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?

confused what"{1,#,2,3}"means?> read more on how binary tree is serialized on OJ.

本题注意不能通过测试是否是合法二叉树来修复，而是要通过检查全局二叉树确定哪两个节点的值调换了。

检查全局二叉树就是通过检查哪两个值是不按由小到大的顺序的。

可以利用额外空间O(n)空间，也可以使用常量空间。

要点就是：利用一个数组如vector保存不合法的节点，最后恢复不合法节点。

如下面两个程序：

1 O(n)空间

void recoverTree(TreeNode *root) 
	{
		if (!root || !root->left && !root->right) return;

		vector<TreeNode *> v;
		getTreeVals(v, root);
		checkVals(v);
	}
	void getTreeVals(vector<TreeNode *> &v, TreeNode *root)
	{
		if (!root) return;
		getTreeVals(v, root->left);
		v.push_back(root);
		getTreeVals(v, root->right);
	}
	void checkVals(vector<TreeNode *> &v)
	{
		int n1 = -1, n2 = -1;
		//画表，根据各种情况，最后得出计算公式
		for (int i = 0; i < v.size()-1; i++)
		{
			if (v[i]->val > v[i+1]->val) 
			{
				if (n1 == -1) n1 = i;
				else n2 = i+1;
			}
		}
		if (n2 == -1) n2 = n1+1;
		swap(v[n1]->val, v[n2]->val);
	}

2 常量空间

void recoverTree(TreeNode *root) 
	{
		if (!root || !root->left && !root->right) return;

		vector<TreeNode *> v;
		TreeNode *p = nullptr;
		getTreeVals(v, root, p);
		swap(v.front()->val, v.back()->val);
	}
	void getTreeVals(vector<TreeNode *> &v, TreeNode *root, TreeNode *&pre)
	{
		if (!root) return;
		getTreeVals(v, root->left, pre);
		if (pre && pre->val > root->val) 
		{
			if (v.empty()) v.push_back(pre);
			v.push_back(root);
		}
		pre = root;
		getTreeVals(v, root->right, pre);
	}

//2014-2-15 update
	void recoverTree(TreeNode *root) 
	{
		vector<TreeNode *> nodes;
		TreeNode *p = NULL;
		getNodes(nodes, root, p);
		swap(nodes.front()->val, nodes.back()->val);
	}
	void getNodes(vector<TreeNode *> &nodes, TreeNode *r, TreeNode *&pre)
	{
		if (!r) return;
		getNodes(nodes, r->left, pre);
		if (pre && pre->val > r->val) 
		{
			nodes.push_back(pre);
			nodes.push_back(r);
		}
		pre = r;
		getNodes(nodes, r->right, pre);
	}