Morris Traversal-常量空间下遍历二叉树

本文主要是介绍Morris Traversal-常量空间下遍历二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

通常遍历二叉树有前序（preorder）、中序（inorder）、后序（postorder）遍历有两个常用的方法：一是递归(recursive)，二是使用栈实现的迭代版本(stack+iterative)。这两种方法都是O(n)的空间复杂度（递归本身占用stack空间或者用户自定义的stack）。递归的方法很简单，栈使用的方法见楼主另一篇文章，栈和队列在遍历二叉树中的使用。文章总结了常见的几种思路给大家参考。但这些方法都在空间复杂度为O(n)，这里还有另一种经典算法，可以做到常数空间使用下遍历，并且时间复杂度仍是线性。就是Morris Traversal。
二叉树遍历最重要的问题就是如何访问完子节点后再回到母结点，否则没法访问其他的子节点。这个问题也叫回溯。之前我们使用栈来存储节点，按照适当的顺序弹出就行，现在使用常量空间，Morris的方法是利用叶子节点的空指针指向相关的母结点，从而完成回溯。下面按照三种遍历分别给出源码及过程。

一、中序遍历

步骤：
1. 如果当前结点的左孩子为空，输出当前节点，并将右孩子作为当前节点；
2. 如果当前节点的左孩子不为空，在当前节点的左子树中寻找当前节点在中序遍历下的前驱节点：
（1）如果前驱节点的右孩子为空，那么将当前节点设为该节点的右孩子，当前节点的左孩子作为新的当前节点。
（2）如果前驱节点的右孩子为当前节点，那么证明已经访问过左子树，输出当前节点，然后当前节点为自己的右孩子。
3. 重复1.2，直至当前节点为空。

void inorderMorrisTraversal(TreeNode *root) {TreeNode *cur = root, *prev = NULL;while (cur != NULL){if (cur->left == NULL)          // 1.{printf("%d ", cur->val);cur = cur->right;}else{// find predecessorprev = cur->left;while (prev

这篇关于Morris Traversal-常量空间下遍历二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---