Morris算法先序、中序遍历二叉树

常见的二叉树遍历算法有递归非递归形式，但实际内部都是要通过栈来进行存储，而Morris算法只需要O(1)的空间复杂度，通过调整叶子节点的指针即可完成二叉树的遍历。

如上图所示，4 5 6都是叶子节点，他们的left，right都指向None,我们可以将right指针利用起来，将叶子节点的right 指针指向下一个待访问的节点，这样我们就不需要用栈，就可以挨个遍历二叉树的所有节点。
Morris算法的要点如下：

• 每个非叶子节点被访问两次(除了第二条中的情况)，第一次访问时为了找到该节点的左子树的最右节点并将该节点的right指针指向当前节点。第二次是通过上个节点的right指针过来的。
  以先序遍历为例比如上图中的节点2，第一次访问是通过1left指针到达的，第二次访问时通过4的right指针到达的
• （先序和中序遍历中）当节点的左子树为None时立即访问该节点
• 每条边访问了两次，用时间换空间
• 第二次访问节点的时候，再次找到左子树的最右节点，此时该节点right指针被指向了当前节点，我们要将他复原

先序遍历

class Solution:
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        pNode = root
        while(pNode):
            if pNode.left == None:
            #左子树为空的时候直接访问，并将指针移动到右子树的根节点
                res.append(pNode.val)
                pNode = pNode.right
            else:
            #因为左子树不为空，所以我们能找到左子树的最右节点
                tmp = pNode.left
                while(tmp.right and tmp.right != pNode):
                    tmp = tmp.right
                if tmp.right == None:
                #注意这里当tmp.right ==None时才访问，因为先序遍历中，这是第一次访问根节点，等第二次访问的时候左子树已经访问完了
                    res.append(pNode.val)
                    tmp.right =pNode
                    pNode = pNode.left
                else:
                # tmp.right ==pNode，表示这是第二次访问根节点了，进行还原操作
                    tmp.right = None
                    pNode = pNode.right
        return res

中序遍历

与先序遍历只有一点点不同，第二次访问到节点的时候才读取它的值。

class Solution:
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        pNode = root
        while(pNode):
            if pNode.left == None:
                res.append(pNode.val)
                pNode = pNode.right
            else:
                tmp = pNode.left
                while(tmp.right and tmp.right!=pNode):
                    tmp = tmp.right
                if tmp.right == None:
                    tmp.right = pNode
                    pNode = pNode.left
                else:
                    res.append(pNode.val)
                    tmp.right =None
                    pNode = pNode.right
        return res