二叉树遍历之图解Mirror算法(莫里斯算法)

本文主要是介绍二叉树遍历之图解Mirror算法(莫里斯算法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

144. 二叉树的前序遍历

我们写二叉树的遍历时，一般有两种方式，迭代和递归。然而还有一种神奇的算法，也可以作我们的二叉树递归，且空间复杂度为O(1)，要知道，我们迭代和递归都是需要额外栈空间的

递归和迭代网上都有很多的资料，虽然莫里斯算法资料是有，但是很少有图解，我们理解起来就会非常困难。下面这篇文章我们主要针对的就是我们的Mrror算法(莫里斯算法)

Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减

我们先给出具体的算法思想，读者可以试着去理解。然后再来看图解，这样的话就会豁然开朗。

假设当前节点为cur，并且开始时赋值为根节点root(其实也可以直接对root操作)。
循环判断cur不为空

if左子树为空，则cur向右孩子移动
if左子树不为空，找到左子树的最右节点(也就是左子树一直往右走的，走到到尽头就是它的最右节点)
如果最右节点的右指针为空，则把右指针指向cur，cur向左孩子移动
如果最右节点的右指针为cur本身，则说明已经访问过一遍了，我们将其置为null，cur向右孩子移动

cur为空时，退出循环

如果我们只看上面的过程的话，相信我们是很难看懂的，下面我们用图解来一步一步解析：
在这里插入图片描述
初始化我们root节点在根节点位置，将1加入结果集中，下面我们判断左子树不为空，则找到左子树的最右节点

找到左子树的最右节点后，我们判断最右节点是否为空，或则为root本身。这里我们为空，所以将最右节点指向root，root向左子树移动。继续循环
在这里插入图片描述
现在我们循环到了3这个节点，左子树为空，我们就转向它的右子树

此时我们的节点走到了5的位置，左子树为空，继续走右子树：

此时我们的根节点到了2的位置，找他的左子树最右节点为5,5的右孩子为root本身，说明前面我们已经走过一次了，断开5的右孩子(5.right=null)，此时我们节点往右孩子走。依次循环，直到root为空，则结束。读者可以自行模拟以下过程，此处我们就不再介绍了。

这里我们并没有给出什么时候将节点加入结果集，因为前中后序都可以采用这种方法遍历，什么时候将节点加入结果集则看它是什么方式遍历，加的位置也不一样

从上面的图解中，我们可以看到它将每个左子树的最右节点进行了利用，相当于给了我们一条回来的路。而看这条路是不是我们走过的，则通过左子树的最右节点是不是指向自身来判断。

LeetCode核心代码实现：

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res=new ArrayList<>();if(root==null)return  res;TreeNode cur=root;TreeNode temp=null;while(cur!=null){if(cur.left==null){//左子树为空res.add(cur.val);cur=cur.right;}else{temp=cur.left;//左子树不为空while(temp.right!=null&&temp.right!=cur){temp=temp.right;}if(temp.right==cur){temp.right=null;cur=cur.right;}else{res.add(cur.val);temp.right=cur;cur=cur.left;}}}return res;}
}