Morris遍历

morris遍历原理参考此处：Morris遍历_六甲横宝的博客-CSDN博客_morris遍历

下面给出用morris遍历实现二叉树的前中后序遍历代码：

前序：

vector<int> morrisPreOrder(TreeNode *root) {
	vector<int> res;
	TreeNode *cur = root, *mostRight = nullptr;
	while (cur) {
		mostRight = cur->left;
		if (mostRight) { //左子树不为空，cur会到达两次
			while (mostRight->right&&mostRight->right != cur) {
				mostRight = mostRight->right;
			}
			if (mostRight->right == nullptr) {
				mostRight->right = cur;
				res.push_back(cur->val); //第一次到的时候打印
				cur = cur->left;
				continue;
			}
			else {  
				mostRight->right = nullptr;  //第二次到的时候不打印
			}
		}
		else { //左子树为空，cur只会到达一次
			res.push_back(cur->val);
		}
		// cur没有左子树或其左子树最右节点的right指针指向cur，均要将cur右移
		cur = cur->right; 
	}
	return res;
}

中序：

vector<int> morrisInOrder(TreeNode *root) {
	vector<int> res;
	TreeNode *cur = root, *mostRight = nullptr;
	while (cur) {
		mostRight = cur->left;
		if (mostRight) { //左子树不为空，cur会到达两次
			while (mostRight->right&&mostRight->right != cur) {
				mostRight = mostRight->right;
			}
			if (mostRight->right == nullptr) {
				mostRight->right = cur;
				cur = cur->left; //第一次到的时候不打印
				continue;
			}
			else {  
				res.push_back(cur->val); //第二次到的时候打印
				mostRight->right = nullptr;
			}
		}
		else { //左子树为空，cur只会到达一次
			res.push_back(cur->val);
		}
		// cur没有左子树或其左子树最右节点的right指针为cur，均要将cur右移
		cur = cur->right;
	}
	return res;
}

后序：

先右后左的前序遍历，再反转即得到后序遍历

//先右后左的前序遍历，反转后就是后序遍历
vector<int> morrisPostOrder(TreeNode *root) {
	vector<int> res;
	TreeNode *cur = root, *mostLeft = nullptr;
	while (cur) {
		mostLeft = cur->right;
		if (mostLeft) { //右子树不为空，cur会到达两次
			while (mostLeft->left&&mostLeft->left != cur) {
				mostLeft = mostLeft->left;
			}
			if (mostLeft->left == nullptr) {
				mostLeft->left = cur;
				res.push_back(cur->val);  //第一次到的时候打印
				cur = cur->right;
				continue;
			}
			else {
				mostLeft->left = nullptr; //第二次到的时候不打印
			}
		}
		else { //右子树为空，cur只会到达一次
			res.push_back(cur->val);
		}
		//cur右子树为空或者右子树最左节点的left指针为cur，均要将cur左移
		cur = cur->left;
	}
	reverse(res.begin(), res.end());  //反转
	return res;
}