导航：首页 > 互联网科技 >

golang刷leetcode 技巧之如何实现特定深度节点链表

发表于：2025-02-04 作者：千家信息网编辑

千家信息网最后更新 2025年02月04日，这篇文章主要为大家展示了"golang刷leetcode 技巧之如何实现特定深度节点链表"，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下"golang刷lee

千家信息网最后更新 2025年02月04日golang刷leetcode 技巧之如何实现特定深度节点链表

这篇文章主要为大家展示了"golang刷leetcode 技巧之如何实现特定深度节点链表"，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下"golang刷leetcode 技巧之如何实现特定深度节点链表"这篇文章吧。

给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。

示例：

输入：[1,2,3,4,5,null,7,8]

/ \

2 3

/ \ \

4 5 7

输出：[[1],[2,3],[4,5,7],[8]]

解题思路

1，这是一道树的层序遍历＋链表的组合题，主要考察树、队列、链表的理解、以及这几种数据结构的综合应用。

2，树的层序遍历，需要借助队列，对于每一层都分开需要借助两个队列

3，遍历的时候，我们将q1 这一层的每一个节点依次弹出，放入链表

4，将每一个节点的左右孩子依次存入q2

5，将q2存入q1

6，重复3～5，直到每个队列都为空为止。

代码实现

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } *//** * Definition for singly-linked list. * type ListNode struct { *     Val int *     Next *ListNode * } */func listOfDepth(tree *TreeNode) []*ListNode {    var q1,q2 queue    if tree==nil{        return nil    }     var r []*ListNode    q1.push(tree)    head:=new(ListNode)    for !q1.empty() || !q2.empty(){        cur:=head        for !q1.empty(){            x:=q1.pop()            if x.Left!=nil{                q2.push(x.Left)            }            if x.Right!=nil{                q2.push(x.Right)            }            cur.Next=&ListNode{              Val:x.Val,            }            cur=cur.Next        }        r=append(r,head.Next)        head.Next=nil        for !q2.empty(){            q1.push(q2.pop())        }    }    return r}
type queue struct{    data []*TreeNode}
func(this*queue)push(t*TreeNode){   this.data=append(this.data,t)}
func (this*queue)empty()bool{    return len(this.data)<1}
func (this*queue)pop()*TreeNode{    if this.empty(){        return nil    }    x:=this.data[0]    this.data=this.data[1:]    return x}