面试题 04.03. 特定深度节点链表【广度优先搜索算法BFS】

题目

思路

就是将树的每一层，都打印成一个链表；
BFS；
BFS的算法思想：
1、根节点压入队列；
2、只要队列不空，处理；
处理队列中的每一个节点（队列中的节点都是同一层的）；
队列中的每一个节点的子节点，入临时队列；
用临时队列替换队列；
重复步骤2；

代码

package main

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

type ListNode struct {
    Val int
    Next *ListNode
}

const PreAllocSize = 2

func listOfDepth(tree *TreeNode) []*ListNode {
    return bfs(tree)
}

// 广度优先搜索算法
func bfs(tree *TreeNode) []*ListNode {
    // 首先要构造一个队列，使用slice构造，并将顶点入队
    queue := []*TreeNode{tree}
    // 存放结果
    res := make([]*ListNode, 0, PreAllocSize)

    // 队列不空就处理，队列里的都是同一层的节点
    for len(queue) > 0 {

        node := new(ListNode)                           // 空的结果队列头
        tmpNode := node                                 // 相当于指针
        tmpQueue := make([]*TreeNode, 0, PreAllocSize)  // 下层节点的临时存放队列, 不能是局部变量

        // 访问所有节点（属于同一层）
        for i := range queue {
            tmpNode.Next = &ListNode{Val: queue[i].Val}
            tmpNode = tmpNode.Next  // 指针后移

            // 当前节点的子节点入临时队列
            if queue[i].Left != nil {
                tmpQueue = append(tmpQueue, queue[i].Left)
            }

            if queue[i].Right != nil {
                tmpQueue = append(tmpQueue, queue[i].Right)
            }
        }

        // 队列替换为下一层队列
        queue = tmpQueue
        res = append(res, node.Next)   // 注意，node是一个空的头，所以node.Next才是第一个头
    }

    return res
}