Morris算法golang版本

Morris算法golang版本

type TreeNode struct{
    Val int
    Left *TreeNode
    Right *TreeNode
}
//中序遍历
func inorderTraversal(root *TreeNode) []int{
    var r []int
    for root != nil{
        if root.left != nil{
            pre := root.Left
            for pre.Right != nil && pre.Right != root{
                pre = pre.Right
            }
            if pre.Right == nil{
                pre.Right = root
                root = root.Left
            }else{
                pre.Right = nil
                r = append(r,root.Val)
                root = root.Right
            }
        }else{
            r = append(r,root.Val)
            root = root.Right
        }
        return r
    }
}
//前序遍历
func preorderTraversal(root *TreeNode) []int{
    var r []int
    for root != nil{
        if root.Left != nil{
            pre := root.Left
            for pre.Right != nil && pre.Right != root{
                pre = pre.Right
            }
            if pre.Right == nil{
                r = append(r,root.Val)
                pre.Right = root
                root = root.Left
            }else{
                pre.Right = nil
                root = root.Right
            }
        }else{
            r= append(r,root.Val)
            root = root.Right 
        }
    }
    return r 
}
//后序遍历
func postorderTraversal(root *TreeNode) []int{
    var r []int
    tmp := root
    for root != nil{
        if root.Left != nil{
            pre := root.Left
            for pre.Right != nil && pre.Right != root{
                pre = pre.Right
            }
            if pre.Right == nil{
                pre.Right = root
                root = root.Left
            }else{
                pre.Right = nil
                rv := reverse(root.Left)
                for rv != nil{
                    r = append(r,rv.Val)
                    rv = rv.Right
                }
                reverse(rv)
                root = root.Right
            }
        }else{
            root = root.Right
        }
    }
    rv := reverse(tmp)
    for rv ! = nil{
        r = append(r,rv.Val)
        rv = rv.Right 
    }
    reverse(rv)
    return r
}

func reverse(root *TreeNode) *TreeNode{
    if root == nil{
        return nil 
    }
    next :=root.Right
    root.Right = nil
    for next != nil{
        tmp := next.Right
        next.Right = root
        root = next
        next = tmp
    }
    return root
}