本文主要是介绍给定一个二叉树，返回每层上节点的链表，设计算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：
1、链表存储每层节点的数据，这样保证指针后移，进行存储该层的节点。
2、遍历上层的节点，通过队列的pull跟add，遍历该层的节点后pull出，同时添加上下个循环要遍历的节点（下层的父节点）。
具体代码如下：
import java.util.*;public class ListTreeNodeDepth {/*** 时间复杂度 o(n) 空间复杂度o(n)* @param args*/public static void main(String[] args) {TreeNode root = new TreeNode(1);TreeNode left1 = new TreeNode(2);TreeNode right1 = new TreeNode(3);TreeNode left2 = new TreeNode(4);TreeNode left3 = new TreeNode(5);TreeNode right2 = new TreeNode(7);TreeNode left4 = new TreeNode(8);root.left = left1;root.right = right1;left1.left = left2;left1.right = left3;right1.right = right2;left2.left = left4;ListNode[] list = listOfDepth(root);for (ListNode node:list) {List<Integer> l = new ArrayList<Integer>();l.add(node.value);while (node.next!=null) {l.add(node.next.value);node.next = node.next.next;}System.out.println(Arrays.toString(l.toArray()));}}/*** 节点*/static class TreeNode {int value;TreeNode left;TreeNode right;TreeNode(int v) {value = v;}}/*** 链表，存储每层的节点*/static class ListNode {int value;ListNode next;ListNode(int v) {value = v;}}/*** 利用队列的pull跟add,推拉来控制每层遍历的节点，并添加到每层的链表中*/public static ListNode[] listOfDepth(TreeNode root) {if (root == null) {return null;}//BFS中的队列Queue<TreeNode> queue = new LinkedList<>();//先把根节点入队，然后执行“弹一个，加n个”queue.add(root);//存放每个链表第一个有实际值(非哑元)节点的容器,ArrayList实际上是一个可变长的数组List<ListNode> list = new ArrayList<>();//只要队列中还有元素就要不停的出队，直到队列中的所有元素都已出队while (!queue.isEmpty()) {//当前队列的长度，即当前层元素的总个数int size = queue.size();//链表的头结点，不放实际的值（哑元）ListNode head = new ListNode(0);//链表移动指针，让它始终指向当表链表的最后一个元素ListNode p = head;//将当前层的节点逐个出队，把出队节点的子节点入队for (int i = 0; i < size; i++) {TreeNode poll = queue.poll();//链表元素追加p.next = new ListNode(poll.value);//指针向后移动一个元素，使p指向链表末尾p = p.next;if (poll.left != null) {//当前出队的节点有左孩子，则左孩子入队queue.add(poll.left);}if (poll.right != null) {//当前出队的节点有右孩子，则右孩子入队queue.add(poll.right);}}//for循环走完后就遍历完了一层，将存储该层节点的链表第一个有实际值的节点入队list.add(head.next);}//将可变长的数组转化成定长数组（因为函数的返回值要求了返回一个定长数组ListNode[]）return list.toArray(new ListNode[list.size()]);}}
参考：https://leetcode-cn.com/problems/list-of-depth-lcci/
https://blog.csdn.net/qq_43988642/article/details/108098431
这篇关于给定一个二叉树，返回每层上节点的链表，设计算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
