[数据结构与算法]Golang前序遍历+后序遍历(N叉树)中序遍历(二叉树) 统一规范化写法 迭代法

前序遍历：

采用stack（先进后出），从子节点反序灌入

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func preorder(root *Node) []int {

    stack := make([]*Node, 0)
    res := make([]int, 0)
    if root == nil{
        return res
    }
    stack = append(stack, root)
    for len(stack)!=0{
        curr := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, curr.Val)
        childList := curr.Children
        for i:=len(childList)-1; i>=0; i--{
            stack = append(stack, childList[i])
        }
    }
    return res
}

后序遍历

采用stack，子节点正序灌入，最后把所有结果进行倒序输出

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func postorder(root *Node) []int {
    stack := make([]*Node, 0)
    res := make([]int, 0)
    if root == nil{
        return res
    }
    stack = append(stack, root)
    for len(stack)>0{
        curr := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, curr.Val)
        childList := curr.Children
        for i:=0; i<len(childList); i++{
            stack = append(stack, childList[i])
        }
    }
    for i,j:=0,len(res)-1; i<j; i, j = i+1,j-1{
        res[i], res[j] = res[j], res[i]
    }
    return res
    
}

中序遍历

先把左边的开到底，没了再加入当前节点，循环条件为curr!=nil || len(stack)>0

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    stack := make([]*TreeNode, 0)
    res := make([]int, 0)
    for root !=nil || len(stack)>0{
        for root != nil{
            stack = append(stack, root)
            root = root.Left
        }
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, root.Val)
        root = root.Right
    }
    return res

}