107. 二叉树的层序遍历 II Golang实现

时间:2024-11-21 17:34:48

题目描述:

给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

输入:root = [3,9,20,null,null,15,7]
输出:[[15,7],[9,20],[3]]

思路分析:

这个题主要还是二叉树的层序遍历问题。二叉树的层序遍历使用队列来进行模拟即可,出队一个的同时将这个节点孩子节点全部加入队列。
但是他要求逆序输入,所以有两个做法:1.在插入的时候采用头插法进行插入。2.插入后使用逆序遍历一次即可。
重点记住层序遍历的大概逻辑:通过记录当前队列的长度来确定一次遍历出队的节点数量(一层的节点数量)

头插法的实现

res = append([][]int{tem},res... ) tem是[]int{}
res...的作用是将一个切片展开,res是二维切片,展开后每个元素就是一个一维切片,然后append的第一参数是目标切片,将第二个元素添加到第一个参数后。从而实现头插的作用。

点击查看代码
func levelOrderBottom(root *TreeNode) [][]int {
    res,line:=[][]int{},[]*TreeNode{}
    if root==nil {
        return [][]int{}
    }
    line = append(line, root)
    for len(line)>0 {
        levelSize,tem := len(line),[]int{}
        for i := 0; i < levelSize; i++ {
            node := line[0]
            line = line[1:]
            if node != nil {
                tem = append(tem, node.Val)
            }
            if node.Left != nil {
                line = append(line, node.Left)
            }
            if node.Right != nil {
                line = append(line, node.Right)
            }
        }
        //双端队列适合无法进行翻转的场景,直接使用头插法
        //res = append([][]int{tem},res... )
        res = append(res, tem)
    }
    // 最后反转层次结果
    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
}