Morris算法进行二叉树遍历

介绍

二叉树作为计算机中的一个重要的数据结构，在很多领域都会涉及到，而提到二叉树，我们首先想到的就是其3种遍历方式—前序、中序和后序，对于这三种遍历方式，我们很容易通过使用递归或者迭代（http://blog.csdn.net/yangfeisc/article/details/44497429）的方式实现，时间复杂度为O(N)。但是这两种实现方式都需要使用堆栈进行节点信息的存储，即空间复杂度也是O(N)。

但是还有一种更为巧妙的遍历方法，Morris算法，该算法的时间复杂度也是O(N)，但是空间复杂度却能达到最优的O(1)

树的节点定义如下：

class TreeNode:
    def __init__(self, x):
        self.x = x
        self.left = None
        self.right = None

中序遍历

算法步骤

1. 当前节点不为空的前提下，将当前节点设置为：cur_node
   1. cur_node的左节点left_node存在，找到cur_node节点的左子树的最右叶子节点right_node。
   2. 最右叶子节点right_node的右节点为空的情况下，right_node的右节点指向cur_node，当前节点指向左节点。
   3. cur_node的左节点left_node不存在，当前cur_node指向当前节点的右节点。
   4. 如果当前节点cur_node存在左节点，并且左节点的右节点是当前节点cur_node，将当前节点的右节点置为None，当前节点指向右节点。

具体实现方式如下：

class Solution:
    
    def findMode(self, root:TreeNode) -> List[int]:
        res = []
        if not root:
            return
        cur = root
        while cur:
            if not cur.left:
                res.append(cur.val)
                cur = cur.right
            else:
                temp = cur.left
                while temp.right and not temp.right == cur:
                    temp = temp.right
                if not temp.right:
                    temp.right = cur
                    cur = cur.left
                else:
                    res.append(cur.val)
                    temp.right = None
                    cur = cur.right
      	return res