莫里斯遍历

时间复杂度为O(n),时间复杂度为O(1)

对于一般的遍历算法，我们都是利用栈来存储之后需要再次访问的节点。
最差情况下，我们需要存储整个二叉树节点。所以空间复杂度为O(n)。
而Morris遍历则是将空间复杂度降到了O(1)级别。Morris遍历用到了“线索二叉树”的概念，
其实就是利用了叶子节点的左右空指针来存储某种遍历前驱节点或者后继节点。因此没有使用额外的空间。
Morris遍历的算法思想
假设当前节点为cur，并且开始时赋值为根节点root。
1, 判断cur节点是否为空
2, 如果不为空
    1）如果cur没有左孩子，cur向右更新，即（cur = cur.right）
    2）如果cur有左孩子，则从左子树找到最右侧节点pre
  如果pre的右孩子为空，则将右孩子指向cur。pre.right = cur
  如果pre的右孩子为cur，则将其指向为空。pre.right = null。（还原树结构）
3, cur为空时，停止遍历

Morris前序遍历的流程

前序遍历

func PreOrder(root *TreeNode) []int {
    res = []int{}
    if root == nil {
        return res 
   cur := root
   for cur != nil {
      if cur.Left == nil {   // cur节点左节点为nil，转移到右节点
          res = append(res,cur.Val)
         cur = cur.Right
      } else {
         pre := cur.Left
         for pre.Right != nil && pre.Right != cur  { 
            pre = pre.Right
         }
         if pre.Right == nil {
            pre.Right = cur
             res = append(res,cur.Val)
            cur = cur.Left
         } else {
            pre.Right = nil
            cur = cur.Right
         }

      }
   }
       return res
}

中序遍历
**

func InOrder(root *TreeNode) (res []int) {
    if root == nil {
        return
    }
    cur := root
    for cur != nil {
        if cur.Left == nil {
            res = append(res,cur.Val)
            cur = cur.Right
        } else {
            pre := cur.Left
            for pre.Right != nil && pre.Right != cur {
                pre = pre.Right
            }
            if pre.Right == nil {
                pre.Right = cur
                cur = cur.Left
            } else {
                pre.Right = nil
                res = append(res,cur.Val)
                cur =cur.Right
            }

        }
    }
    return res
}

后序遍历
**

func Postorder(root *TreeNode)  []int {
   cur := root
   res := []int{}
   for cur != nil {
      if cur.Right == nil {
         res = append(res,cur.Val)
         cur = cur.Left
      } else {
         pre := cur.Right
         for pre.Left != nil && pre.Left != cur {
            pre = pre.Left
         }
         if pre.Left == nil {
            pre.Left = cur
            res = append(res,cur.Val)
            cur = cur.Right
         } else {
            pre.Right = nil
            cur = cur.Left
         }
      }
   }
    for i:=0;i<len(res)/2;i++ {
        res[i],res[len(res]-1-i]= res[len(res]-1-i], res[i]
   }
    return res 
}