BFS_DEMO

func levelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    tmp := []int{}
    if root == nil {
        return res
    }
    lis := list.New()
    // 根节点添加进去，
    lis.PushBack(root)

    for lis.Len() > 0 {
        // 长度必须保存出来， 不然数组长度是动态的
        l := lis.Len()
        for i := 0; i < l; i++ {
            // 其实这种方式很好，很有弹性，只需要传参数，就可以指定弹出前还是后！！！
            node := lis.Remove(lis.Front()).(*TreeNode2)
            if node.Left != nil {
                // 别在左侧用参数接受了
                lis.PushBack(node.Left)
            }
            if node.Right != nil {
                lis.PushBack(node.Right)
            }
            tmp = append(tmp, node.Val)
        }
        // 二维数组
        res = append(res, tmp)
        // 当前层数据清空
        tmp = []int{}
    }
    return res
}

注意多叉树遍历429哪道题的多叉树节点定义

题目

1.102

leetcode102

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode)(res [][]int){
    // 临时数组初始化
    tmp := []int{}
    // 判空
    if root==nil{
        return res
    }
    lis := list.New()
    lis.PushBack(root)
    for lis.Len()>0{
        // 先把长度存起来，不然一会长度会变化
        l := lis.Len()
        for i:=0;i<l;i++{
            node := lis.Remove(lis.Front()).(*TreeNode)
            if node.Left!=nil{
                lis.PushBack(node.Left)
            }
            if node.Right!=nil{
                lis.PushBack(node.Right)
            }
            // 当前节点添加进临时数组
            tmp = append(tmp, node.Val)
        }
        // 把数组添加进返回的数组
        res = append(res, tmp)
        // 清空当前层
        tmp = []int{}
    }
    return res

}

2.107

leetcode107

func levelOrderBottom(root *TreeNode)(res [][]int) {
    tmp := []int{}
    if root==nil{
        return res
    }
    // 初始化队列
    lis := list.New()
    lis.PushBack(root)
    for lis.Len()>0{
        // 记录长度
        length := lis.Len()
        for i:=0;i<length;i++{
            node := lis.Remove(lis.Front()).(*TreeNode)
            if node.Left!=nil{
                lis.PushBack(node.Left)
            }
            if node.Right!=nil{
                lis.PushBack(node.Right)
            }
            tmp = append(tmp, node.Val)
        }
        res = append(res, tmp)
        tmp = []int{}
    }
    reverse(res)
    return res
}
func reverse(res [][]int){
    left, right := 0, len(res)-1
    for right>left{
        res[left], res[right] = res[right], res[left]
        left++
        right--
    }
}

3.199

leetcode199

<注意：>不能不傻傻的不遍历左面节点，以为有可能左子树深，而右面浅，导致本应该在结果中添加的左子树节点没添加上
他这个从右侧看，如果左侧子树深的话会出现在结果数组里

func rightSideView(root *TreeNode) []int {
    res := []int{}
    if root==nil{
        return res
    }
    lis := list.New()
    lis.PushBack(root)
    for lis.Len()>0{
        length := lis.Len()
        for i:=0;i<length;i++{
            node := lis.Remove(lis.Front()).(*TreeNode)
            // 不能不傻傻的不遍历左面节点，以为有可能左子树深，而右面浅，导致本应该在结果中添加的左子树节点没添加上
            if node.Left!=nil{
                lis.PushBack(node.Left)
            }
            if node.Right!=nil{
                lis.PushBack(node.Right)
            }
            // 每次只取最后一个元素
            if i==length-1{
                res = append(res, node.Val)
            }
        }
    }
    return res
}

4.637

leetcode:637

有一个点需要注意，average返回值为float64,必须提前转换类型，不然会精度丢失

func averageOfLevels(root *TreeNode) []float64 {
    res := []float64{}

    if root == nil{
        return res
    }
    // 初始化临时数组
    tmp := []float64{}
    var t float64
    // 初始化 队列
    lis := list.New()
    lis.PushBack(root)
    // 进入循环，Bfs,
    for lis.Len()>0{
        // length赋值到其他变量保存
        length := lis.Len()
        for i:=0;i<length;i++{
            node := lis.Remove(lis.Front()).(*TreeNode)
            if node.Left!=nil{
                lis.PushBack(node.Left)
            }
            if node.Right!=nil{
                lis.PushBack(node.Right)
            }
            tmp = append(tmp, float64(node.Val))
        } 
        t = average(tmp)
        // fmt.Println(t)
        res = append(res, t)
        tmp = []float64{}
    }
    return res
}

func average(res []float64)(ret float64){
    // length
    leng := len(res)
    // tmp
    var tmp float64
    // average
    for _, v := range res{
        tmp += v
    }
    // fmt.Println("len:", leng)
    // fmt.Println("res", res)
    return tmp/float64(leng)
}

5.429多叉树遍历

leetcode:429

多叉树遍历其实也是一道模板提，和二叉树是一个道理，
只不过二叉树是添加左右子节点，多叉树是添加数组

 type Node struct {
     Val int
     Children []*Node
  }

func levelOrder(root *Node) [][]int {
    res := [][]int{}
    if root == nil{
        return res
    }
    tmp := []int{}
    lis := list.New()
    lis.PushBack(root)
    for lis.Len()>0{
        length := lis.Len()
        for i:=0;i<length;i++{
            node := lis.Remove(lis.Front()).(*Node)
            tmp = append(tmp, node.Val)
            // 因为存的不是左右子节点了。是一个数组，要遍历添加
            for j := 0;j<len(node.Children);j++{
                lis.PushBack(node.Children[j])
            }
        }
        res = append(res, tmp)
        tmp = []int{}
    }
    return res
}