题解 | #实现二叉树先序，中序和后序遍历# go + 迭代

go + 迭代

package main
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 
 * @param root TreeNode类 the root of binary tree
 * @return int整型二维数组
*/
func threeOrders( root *TreeNode ) [][]int {
    // write code here
    if root == nil {
        return nil
    }

    ret := make([][]int, 0)
    ret = append(ret, pre(root), middle(root), suff(root))

    return ret
}


func pre(root *TreeNode) []int {
    r := make([]int, 0)

    stack := []*TreeNode{root}

    for len(stack) > 0 {
        top := stack[len(stack)-1]
        if top != nil {
            stack = stack[:len(stack)-1]

            if top.Right != nil {
                stack = append(stack, top.Right)
            }
            if top.Left != nil {
                stack =append(stack, top.Left)
            }
            stack = append(stack, top, (*TreeNode)(nil))
        }else{
            node := stack[len(stack)-2]
            r = append(r, node.Val)
            stack = stack[:len(stack)-2]
        }
    }

    return r
}


func middle(root *TreeNode) []int {
    r := make([]int, 0)

    stack := []*TreeNode{root}

    for len(stack) > 0 {
        top := stack[len(stack)-1]
        if top != nil {
            stack = stack[:len(stack)-1]

            if top.Right != nil {
                stack = append(stack, top.Right)
            }
            stack = append(stack, top, (*TreeNode)(nil))
            if top.Left != nil {
                stack =append(stack, top.Left)
            }
        }else{
            node := stack[len(stack)-2]
            r = append(r, node.Val)
            stack = stack[:len(stack)-2]
        }
    }

    return r
}

func suff(root *TreeNode) []int{
    r := make([]int, 0)

    stack := []*TreeNode{root}

    for len(stack) > 0 {
        top := stack[len(stack)-1]
        if top != nil {
            stack = stack[:len(stack)-1]
            stack = append(stack, top, (*TreeNode)(nil))

            if top.Right != nil {
                stack = append(stack, top.Right)
            }
            if top.Left != nil {
                stack =append(stack, top.Left)
            }
        }else{
            node := stack[len(stack)-2]
            r = append(r, node.Val)
            stack = stack[:len(stack)-2]
        }
    }

    return r
}