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.

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);
	}

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);
	}

Leetcode Recover Binary Search Tree

原文：http://blog.csdn.net/kenden23/article/details/17580561