算法:Morries法遍历二叉树

今天看了下左神讲的有关morries遍历二叉树的视频(morries遍历，学术上就是线索化遍历二叉树)，这种遍历方法没有用到其他辅助数据结构，只使用了叶子结点的空闲指针，节省了许多不必要的开销，同时也加快了遍历的时间效率，下面我来总结

核心要点(步骤)

1. 初始化线索结点，名字叫做cur，指向树的根结点
2. 如果cur没有左孩子，cur右移，cur指向cur的右孩子结点(cur = cur->right)
3. 如果cur有左孩子，重点来了，找到cur左子树上的最右的孩子结点，名字叫做mostRight
4. 如果mostRight的右孩子为空，让右指针指向cur，cur左移(cur = cur->left)
5. 如果mostRight的右孩子指向cur，让其右指针重新置为空，cur右移(cur = cur->right)
6. 如果cur为空，遍历结束

前序遍历模板

void morris(TreeNode* root){
	if(!root){
		return;
	}
	TreeNode* cur = root;
	TreeNode* mostright = nullptr;
	while(cur){
		mostright = cur->left;
		if(mostright){
			while(mostright->right && mostright->right!=cur){
				mostright = mostright->right;
			}
			if(!mostright->right){
				mostright->right = cur;
				cout<<cur->val;
				cur = cur->left;
				continue;
			}else{
				mostright->right = nullptr;
			}
		}else{
			cout << cur->val;
		}
		cur = cur->right;
	}
}

图表示步骤

由于morries遍历有个特点，对于有左右孩子的结点，这个结点会有两次机会被遍历到，而叶子结点就只能被遍历到一次，所以要注意输出打印语句的时机，今天就写这么多，有点困，下次补充叭