golang 刷leetcode：Morris 遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]

输出：[1,3,2]

示例 2：

输入：root = []

输出：[]

示例 3：

输入：root = [1]

输出：[1]

提示：

树中节点数目在范围 [0, 100] 内

-100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

空间复杂度O（1）完成中序遍历Morries遍历

过程：

1，如果左孩子非空，让左孩子的最右节点指向根节点得到左孩子的最右节点

2，如果最右节点的右孩子节点是null，说明是第一次遍历，把它的右孩子指向根节点

3，如果最右节点的右孩子是当前节点，说明，是第二次遍历，把最右节点的右孩子指向空，即还原树

4，如果左孩子为空，将当前节点移动到右节点。

5，左孩子为空父亲节点遍历一次，第一就取值，左孩子非空由于会遍历父亲节点两次，所以第二次到达父亲节点的时候取值，就实现了中序遍历。

实现：

/**
 * Definition for a binary tree node.
 * 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
}

复制

同理先序遍历，就是第一次到达父亲节点的时候取值

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
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
}

复制

后序序遍历，需要在第二次到达父亲节点的时候，逆序保存，最右孩子到父亲节点的值,遍历完后，需要保存从根节点到最右孩子的逆序：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
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
}

复制