二叉树Morris遍历代码记录

• Morris序可以判断出是第几次到达这个节点，有什么用处呢？

在二叉树的学习中大家都知道存在前中后序遍历，这三种遍历方式的递归实现都不需要判断是第几次到达节点，因为有函数递归的栈帧保证了三次访问。
而非递归实现方式中就需要额外记录节点是第几次被访问，这时候Morris遍历就发挥出作用了。

前序遍历的结果就是Morris遍历中每个节点第一次到达即打印的结果。
中序遍历的结果就是Morris遍历如果只能到达一次就打印，可到达两次就第二次到达时打印的结果。如何判断？判断节点如果没有左孩子，它只可到达一次，直接打印即可。

ListNode *morris(ListNode *head) {
	ListNode *cur = head;
	ListNode *mostRight = nullptr;

	while (cur != nullptr) {
		mostRight = cur->left;
		// 判断cur有无左树
		if (mostRight != nullptr) {
			// 有左树，找到真实最右节点
			while (mostRight->right != nullptr && mostRight->right != cur) {
				mostRight = mostRight->right;
			}
			// 从while跳出，说明mostRight是左树最右节点
			//   第一次来到此节点
			if (mostRight->right == nullptr) {
				mostRight->right = cur;
				cur = cur->left;
				continue;		// 回到大while，此时为原cur的左孩子
			} else {
				mostRight->right = nullptr;
			}
		}
		cur = cur->right;
	}
}

这几天看了左程云老师的讲解，还是介绍比较细致的，对之前二叉树非递归实现不通透的地方也理解了，左神nb

// 待补充