树（一）——Morris 二叉树神级遍历_综合

前言

二叉树的遍历是解决二叉树相关问题难以回避的问题，很多问题都是在遍历的基础上来解决的。根据问题的不同，我们可以采用不同的遍历方式。
按照对根节点操作的顺序可以分成：

先序遍历
中序遍历
后序遍历
层次遍历

按照实现遍历的方式可以分成：

递归：代码简单，易于理解，但是浪费JVM栈内存。
迭代：利用辅助结构，实现遍历，需要设计遍历的顺序。

迭代的方式遍历数组的时间复杂度为O(n)，空间复杂度为O(h)。h为树的高度。Morris遍历的优势在于，不采用辅助结构遍历二叉树，其空间复杂度为O(1)。

为什么可以不采用辅助结构？？

首先思考一下，为什么我们要用栈或者队列来辅助我们遍历？
因为二叉树的结构是，一个父节点可以轻松的找到子节点，但是子节点无法直接找到父节点。我们需要利用栈或者队列保存访问的记录，以便于我们可以回溯到父节点。
Morris 遍历采用多个指针，使得通过复杂度不高的操作可以找到父节点。

Morris 遍历

Morris 遍历是一种节省空间复杂度的方法。将叶子节点上的空指针利用起来，指向父节点，当再次遍历到这个节点的时候再修改回来，这样最后二叉树的结构也没有发生改变。

遍历规则

cur：当前遍历的指针
rightMost：cur节点的左子树的最右节点

如果cur左子树为空：cur=cur.right;
如果cur左子树不为空：找到rightMost
——1）如果rightMost.right=null，那么令rightMost=cur, cur=cur.left;
——2）否则，不为空则说明rightMost.right曾经被修改过，我们这是第二次来到这个点，修改rightMost.right=null,cur=cur.right;

解释一下上面的步骤：

首先整体向左走，如果没有左子树向右走。
如果左子树不为空，那么就找到左子树上最右的节点。这个节点的右子树一定是空的。把这个空指针指向当前节点，即保存了一个指向父节点的指针。此时，左子树还有值没有访问，cur向左走。
3 中的结果是rightMost遍历到这个节点的，cur指针也会遍历到这个节点，这就是第二次访问到了，那么此时该节点作为rightMost时，是被修改过的，所以我们要重新修改其为null。
当出现3的情况时，说明该节点的左子树全部访问完毕，所以此时cur向右走。
cur是真正有效的移动指针，它会走过所有的节点，rightMost是为了修改指针而存在的。

图示

整体上来说是这个样子：如果不考虑指针恢复的操作：在这里插入图片描述

其实不难发现，在这种遍历方式中，有些节点会访问两次，有些节点会访问一次。因为我们有两个指针cur和rightMost，cur会走过所有的节点，rightMost会修改节点指向，使得cur重新访问到某个父节点。
该二叉树的Mirrors序列）（cur走过的顺序）为：
1 2 4 2 5 1 3 6 3 7
在这里插入图片描述

Code

Morris遍历伪代码

 		TreeNode cur = root;while (cur != null) {
    // cur指针来遍历二叉树TreeNode rightMost = cur;// 左子树不为空if (cur.left != null) {
    // 向左走，目的是遍历完左子树rightMost = cur.left;// 找到rightMostwhile (rightMost.right != null && rightMost.right != cur) rightMost = rightMost.right;// 查看right指针是否被修改过来if (rightMost.right == null) {
    rightMost.right = cur;cur = cur.left;// 如果没有被修改过，那么说明这个左子树没有遍历完，continue会使得最下面的cur向右移动执行不到，因为我们不希望想右走，左边子树还没有遍历完呢continue;} // 修改过了，这是第二次到了该节点，我们需要将节点的指针修改回来。rightMost.right = null;}// 如果访问过了，向右走cur = cur.right;}

基于Morris遍历先序

因为所有节点只有俩种情况：访问一次和访问两次
访问一次的节点即没有左子树的节点，那么遇到就打印。
访问两次的节点：有左子树，遇到第一次就打印，第二次不打印

public void morrisPreOrder(TreeNode root) {
    if (root == null) return res;TreeNode cur = root;while (cur != null) {
    if (cur.left != null) {
    TreeNode rightMost = cur.left;// 找到cur的左子树的最右节点，因为我们要通过这个节点返回回来。while (rightMost.right != null && rightMost.right != cur) rightMost = rightMost.right;// 当第一次遍历到rightMost时，我们要建立起其和cur的联系，同时打印cur节点if (rightMost.right == null) {
    // 这里是你对节点的操作System.out.println(cur.val);rightMost.right = cur;cur = cur.left;continue;}// 恢复叶子的空指针rightMost.right = null;} else // 如果当前节点没有左孩子，那么我们不必遍历其左子树，直接输出该节点后开始遍历其右子树即可，因为我们不用返回到该节点了// 这里是你对节点的操作System.out.println(cur.val);cur = cur.right;}
}

基于Morris遍历中序

访问一次的节点即没有左子树的节点，那么遇到就打印。
访问两次的节点：有左子树，遇到第一次不打印，第二次打印

public void morrisInOrder(TreeNode root) {
    if (root == null) return res;TreeNode cur = root;while (cur != null) {
    if (cur.left != null) {
    TreeNode rightMost = cur.left;// 找到cur的左子树的最右节点，因为我们要通过这个节点返回回来。while (rightMost.right != null && rightMost.right != cur) rightMost = rightMost.right;// 当第一次遍历到rightMost时，我们要建立起其和cur的联系，不打印这个节点if (rightMost.right == null) {
    rightMost.right = cur;cur = cur.left;continue;}// 恢复叶子的空指针rightMost.right = null;}// 如果当前节点没有左孩子，那么我们不必遍历其左子树，直接输出该节点后开始遍历其右子树即可，因为我们不用返回到该节点了// 这里是你对节点的操作，这是我们第二次访问这个节点，注意这里没有elseSystem.out.println(cur.val);cur = cur.right;}
}

基于Morris遍历后序

后序相对比较复杂。
整体思路还是基于Morris遍历。
但是：对于被访问一次的节点，不做任何处理。
访问两次的节点，第二次访问时，逆序打印其左子树右边界。
在这里插入图片描述我们来看1的左子树，后序访问顺序为 4,4,5,2，按照Morris访问的顺序来看，当来到4的时候，4的右指针是指向2的，此时，是第二次访问到2节点，我们就逆序打印2的左子树的右边界，此时就到了4，因为4节点是叶子，所以此时输出的内容是4。
接着遍历到下面的4节点，其右指针指向的是1节点。这也是第二次访问到1，逆序打印从2-5-4节点，即1的左子树的右边界。注意此时1并没有打印出来。
到了根节点的右子树也是如此，但是最后无法打印根节点的右边界，所以最后要打印一下，此时也输出了根节点，完全符合后序遍历的结果。
在这里插入图片描述

// 代码来自leetCode二叉树后序遍历public List<Integer> postorderTraversal(TreeNode root) {
    TreeNode cur = root;ArrayList<Integer> res = new ArrayList<>();while (cur != null) {
    TreeNode rightMost = cur.left;if (rightMost != null) {
    while (rightMost.right != null && rightMost.right != cur)rightMost = rightMost.right;if (rightMost.right == null) {
    rightMost.right = cur;cur = cur.left;continue;}rightMost.right = null;function(cur.left,res);}cur = cur.right;}function(root,res);return res;}public void function (TreeNode node, ArrayList<Integer> res) {
    
// 先逆序整个右边界TreeNode tail = reverseEdge(node);TreeNode cur = tail;while (cur != null) {
    res.add(cur.val);cur = cur.right;}
// 翻转回来reverseEdge(tail);}public TreeNode reverseEdge(TreeNode node) {
    TreeNode pre = null;TreeNode next = null;while (node != null) {
    next = node.right;node.right = pre;pre = node;node = next;}return pre;}

参考

程序员代码面试指南（第二版）
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/