n树遍历，前序、后序、层序

    前序遍历

    1. /**
    2.  * Definition for a Node.
    3.  * type Node struct {
    4.  *     Val int
    5.  *     Children []*Node
    6.  * }
    7.  */
    9. //递归
    10. func preorder(root *Node) []int {
    11.     res := []int{}
    12.     if root == nil {
    13.         return res 
    14.     }
    15.     res = append(res,root.Val)
    17.     for _, node := range root.Children {
    18.         res = append(res,preorder(node)...)
    19.     }
    20.     return res 
    21. } 
    23. //迭代 
    25. func preorder(root *Node) []int {
    26.     res := []int{}
    27.     if root == nil {
    28.         return res 
    29.     }
    31.     stack := []*Node{root}
    32.     for len(stack) > 0 {
    33.         node := stack[len(stack)-1]
    34.         stack = stack[:len(stack)-1]
    35.         res = append(res,node.Val)
    36.         for i:=len(node.Children)-1;i>=0;i-- {
    37.             stack = append(stack,node.Children[i])
    38.         }
    39.     }
    40.     return res 
    41. }

    后序遍历

    /**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
// 递归
func postorder(root *Node) []int {
    res := []int{}
    if root == nil {
        return res 
    }
    for _,node := range root.Children {
        res = append(res,postorder(node)...)
    }
    res = append(res,root.Val)

    return res  
}

// 迭代 
func postorder(root *Node) []int {
    res := []int{}
    stack :=[]*Node{root}
    if root == nil {
        return res 
    }
    for len(stack) >0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res,node.Val)
        for _, no := range node.Children {
            stack = append(stack,no)
        }
    }
    for i:=0;i< len(res)/2;i++ {
        res[i],res[len(res)-1-i] = res[len(res)-1-i],res[i]
    }
    return res  
}

    层级遍历

    

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

// 递归 

var res [][]int 
func levelOrder(root *Node) [][]int {
    res = make([][]int,0)
    if root == nil {
        return res
    }
    dfs(root,0)
    return res
}

func dfs(root *Node,level int) {
    if root == nil {
        return 
    }
    if len(res) == level {
        res = append(res,[]int{})
    }
    res[level] = append(res[level],root.Val)
    for _, child := range root.Children {
        dfs(child,level+1)
    }
}


//迭代 
func levelOrder(root *Node) [][]int {
    res := [][]int{}
    if root == nil {
        return res 
    }
    queue := []*Node{}
    queue = append(queue,root)
    for len(queue) >0 {
        length := len(queue) 
        ress := []int{}
        for length >0 {
            node := queue[0]
            queue = queue[1:]
            ress = append(ress,node.Val)
            length-- 
            for _,child := range node.Children {
                queue = append(queue,child)
            }
        }
        res = append(res,ress)
    }
    return res 
}