[数据结构与算法]【力扣算法题】二叉树的中序遍历（莫里斯解法，菜鸡的理解 C++）

莫里斯（Morris）解法的核心思想是将二叉树变成链表结构
其实就是将二叉树的结构，按中序遍历的顺序变为，只有根结点和在同一方向上的N-1个右子树（像下图这种结构）

莫里斯是如何实现这种结构的转换的呢？

大致的过程其实就是将根结点和整个右子树部分，不断转移到左结点的最右的右子树结点的下面（变成它的右子树），直到不存在左子树为止。
（注意：下面的解法是边移动边保存结果，而不是先将其全部转换完再来读取结果）

实现的关键点在于还要弄清这个转换过程中会出现的所有情况：

从根结点开始：

1、左子树不为空，这种情况下又存在两种情况：
1) 左子树右子树不为空：要找到左子树最右边的那个子树，这个结点将会成为移动部分的新的父节点
2）左子树的右子树为空：右边没有子树，那么这个左子树就是移动部分的新的父节点。

移动完成后，根结点变成了原先根结点的左子树结点。
【注意】：移动部分里的左子树也变了，应当提前置空

2、左子树为空：当前的根结点不需要移动操作，将其值加入结果。然后当前结点变为当前结点的右子树，继续新一轮的判断和操作。

直到当前结点为空停止操作，返回存储结果的vector。

下面是实现的代码

vector<int> inorderTraversal(TreeNode* root) {
	//中序遍历-莫里斯解法
	vector<int>rel;

	while (root != nullptr) {
		TreeNode* pre = root->left; 
		TreeNode* temp = pre;
		if (pre != nullptr) //左子树不为空，两种情况1）不存在右子树  2）存在右子树
		{
			while (pre->right != nullptr)
			{
				pre = pre->right;
			}
			root->left = nullptr; //别忘了将移动部分的左子树置空
			pre->right = root;//包含了情况1 
			root = temp; //转移完成，根结点变成左节点
		}
		//左子树为空，加入结果
		if (root->left == nullptr)
		{
			rel.push_back(root->val);
			root = root->right;
		}
	}
    return rel;
    }