本文共 3060 字，大约阅读时间需要 10 分钟。

要实现一个二叉树的每层节点生成链表的算法，可以采用宽度优先搜索（BFS）方法。这种方法通过队列来逐层遍历树的节点，并根据节点所在的层数来构建对应的链表。以下是优化后的详细步骤：

步骤一：初始化队列将根节点加入队列，准备开始广度优先搜索。

步骤二：遍历队列使用一个循环处理队列中的每个节点，直到队列为空。

步骤三：处理当前节点对于每个节点，检查其当前层数是否等于目标层数：

• 如果等于目标层数，开始构建该层的链表。如果链表为空，创建一个新的链表头并将当前节点作为链表的第一个节点。否则，将当前节点添加到链表的末尾。
• 如果层数大于目标层数，停止处理，返回当前链表。

步骤四：处理子节点将当前节点的左子节点和右子节点加入队列，同时记录它们的层数（当前层数+1）。

步骤五：返回链表头处理完所有节点后，返回链表的头节点。

优化代码结构

示例代码

import java.util.LinkedList;import java.util.Queue;public class TreeLevel {    public static void main(String[] args) {        // 初始化二叉树        TreeNode root = new TreeNode(1);        TreeNode l = new TreeNode(2);        TreeNode r = new TreeNode(3);        root.left = l;        root.right = r;        l.left = new TreeNode(4);        l.right = new TreeNode(5);        r.left = new TreeNode(6);        r.right = new TreeNode(7);        // 假设我们要获取第3层的节点        int targetDepth = 3;        // 使用广度优先搜索获取指定层级的链表        ListNode head = getTreeLevel(root, targetDepth);        // 输出链表中的节点        if (head != null) {            ListNode p = head;            while (p != null) {                System.out.println(p.getValue());                p = p.getNext();            }        }    }    // 获取指定层级的链表头节点    private static ListNode getTreeLevel(TreeNode root, int targetDepth) {        Queue
   
     queue = new LinkedList<>();        queue.offer(new NodeAndHeight(root, 1));        // 链表头和当前指针        ListNode head = null;        ListNode p = null;        while (!queue.isEmpty()) {            NodeAndHeight current = queue.poll();            // 如果当前层数等于目标层级，开始构建链表            if (current.level == targetDepth) {                if (head == null) {                    head = new ListNode(current.node.getValue());                    p = head;                } else {                    // 创建新的节点并连接到链表末尾                    p.next = new ListNode(current.node.getValue());                    p = p.next;                }            } else if (current.level > targetDepth) {                // 超过目标层级，停止处理                break;            }            // 将子节点加入队列，记录下一层的层数            if (current.node.left != null) {                queue.offer(new NodeAndHeight(current.node.left, current.level + 1));            }            if (current.node.right != null) {                queue.offer(new NodeAndHeight(current.node.right, current.level + 1));            }        }        return head;    }    // 节点和层数的封装类    private static class NodeAndHeight {        private TreeNode node;        private int level;        NodeAndHeight(TreeNode node, int level) {            this.node = node;            this.level = level;        }    }    // 芯联表节点类    private static class ListNode {        private Object value;        private ListNode next;        ListNode(Object value) {            this.value = value;        }    }}
   

代码解释

通过这种方法，不仅实现了每层节点的链表生成，还优化了代码结构，使其更易读和高效。

转载地址：http://hawg.baihongyu.com/