99二叉探索ツリーの復元(中順遍歴+二重ポインタ逆順対+再帰遍歴)

1、テーマの説明
ツリー内の2つのノードが誤って交換されました.
構造を変えずに、この木を復元してください.
ステップ:
O(n)空間複雑度を用いた解法は容易に実現できる.定数空間だけを使う解決策を考え出せますか?
2、例
入力:[3,1,4,null,null,2]
  3  /\1   4   /  2
出力:[2,1,4,null,null,3]
  2  /\1   4   /  3
3、問題解
基本思想:まずスタックの中序に基づいて二叉木を遍歴し、中序遍歴シーケンスmiddleOrderを得、それから二重ポインタに基づいてmiddleOrderシーケンスの中で逆序対swap 1とswap 2を探し、最後に再帰遍歴二叉木に基づいてswap 1とswap 2の2つのノード値を見つけて交換する.

#include
#include
#include
#include
using namespace std;
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
#define inf 9999
void Init_TreeNode(TreeNode** T, vector& vec, int& pos)
{
	if (vec[pos] == inf || vec.size() == 0)
		*T = NULL;
	else
	{
		(*T) = new TreeNode(0);
		(*T)->val = vec[pos];
		Init_TreeNode(&(*T)->left, vec, ++pos);
		Init_TreeNode(&(*T)->right, vec, ++pos);
	}
}
void PreOrderTraverse(TreeNode* T)
{
	if (T == NULL)
		return;
	cout << T->val << " ";
	PreOrderTraverse(T->left);
	PreOrderTraverse(T->right);
}
class Solution {
public:
	void recoverTree(TreeNode* root) {
		//    ：            ，        middleOrder
		//        middleOrder       swap1 swap2
		//             swap1 swap2        
		if (root == NULL)
			return;
		vector middleOrder;
		stack st;
		TreeNode* p = root;
		int swap1 = -1, swap2 = -1;
		//           ，        middleOrder
		while (p != NULL || !st.empty())
		{
			while (p != NULL)
			{
				st.push(p);
				p = p->left;
			}
			p = st.top();
			st.pop();
			middleOrder.push_back(p->val);
			p = p->right;
		}
		//      middleOrder       swap1 swap2
		int i = 0, j = middleOrder.size() - 1;
		while (swap1 == -1 || swap2 == -1)
		{
			if (middleOrder[i] > middleOrder[i + 1])
				swap1 = i;
			else
				i++;
			if (middleOrder[j] < middleOrder[j - 1])
				swap2 = j;
			else
				j--;
		}
		//           swap1 swap2        
		Traverse(root, middleOrder[swap1], middleOrder[swap2]);
	}
	void Traverse(TreeNode* T, int swap1, int swap2)
	{
		if (T == NULL)
			return;
		if (T->val == swap1 || T->val == swap2)
			T->val = T->val == swap1 ? swap2 : swap1;
		Traverse(T->left, swap1, swap2);
		Traverse(T->right, swap1, swap2);
	}
};
int main()
{
	Solution solute;
	TreeNode* root = NULL;
	vector vec = { 3,1,inf,inf,4,2,inf,inf,inf };
	int pos = 0;
	Init_TreeNode(&root, vec, pos);
	solute.recoverTree(root);
	PreOrderTraverse(root);
	return 0;
}