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
  
    v;
		getTreeva ls(v, root);
		checkVals(v);
	}
	void getTreeva ls(vector
   
     &v, TreeNode *root) { if (!root) return; getTreeva ls(v, root->left); v.push_back(root); getTreeva ls(v, root->right); } void checkVals(vector
    
      &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
  
    v;
		TreeNode *p = nullptr;
		getTreeva ls(v, root, p);
		swap(v.front()->val, v.back()->val);
	}
	void getTreeva ls(vector
   
     &v, TreeNode *root, TreeNode *&pre) { if (!root) return; getTreeva ls(v, root->left, pre); if (pre && pre->val > root->val) { if (v.empty()) v.push_back(pre); v.push_back(root); } pre = root; getTreeva ls(v, root->right, pre); }