力扣-面试题 04.03. 特定深度节点链表

Myth丶恋晨 2022-10-11 03:42 129阅读 0赞

这道题换个问法，就是二叉树，如何做广度优先遍历。

> 给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。
> 
> 示例：
> 
> 输入：\[1,2,3,4,5,null,7,8\]
> 
> 1  
> / \\  
> 2 3  
> / \\ \\  
> 4 5 7  
> /  
> 8
> 
> 输出：\[\[1\],\[2,3\],\[4,5,7\],\[8\]\]

在力扣上的测试用例是这样的：

实际上，题的意思就是，你需要把每层的节点的数字，再构造成链表。这给我带来了很大的困扰。可能我对构造链表没有那么熟悉！

## 看题解： ##

1. 先把第一层的一个节点放到辅队列

2. 对于二叉树的广度优先遍历，我们第一要想要的是使用 队列来辅助完成。

进入程序循环体，则当前的队列的长度就是此次循环要处理的节点。

把取到的节点构造成一个链表，用户返回，此时这个链表就是当前层的所有节点

把当前节点的左孩子和右兄弟都放到这个辅助的队列里边，用于下轮的遍历

3. 程序的退出，就是辅助队列里边不再有节点。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode[] listOfDepth(TreeNode tree) {
           	// 目标是打印每层的节点 -> 想要实现这一目标
    		// 我的第一感觉是，如果想要打印当前层，则需要知道上一层的所有的节点，然后分别获取到他们所有节点就可以完成
    		// 广度优先遍历
    
    		Queue<TreeNode> queue = new LinkedBlockingQueue<>();
    		ArrayList<ListNode> result = new ArrayList<>();
    		//  生成这个队列
    		if(tree == null){
    			return null;
    		}
    		queue.add(tree);
    		while (!queue.isEmpty()){
    			int point = queue.size();
    			// 存放当前层，的所有节点的值。
    			TreeNode tempNode = null;
    			ListNode head = new ListNode(0);
    			ListNode nextNode = head;
    			for (int i = 0; i < point; i++) {
    				tempNode = queue.poll();
    				nextNode.next = new ListNode(tempNode.val);
    				nextNode = nextNode.next;
    				if(tempNode.left != null){
    					queue.add(tempNode.left);
    				}
    				if(tempNode.right != null){
    					queue.add(tempNode.right);
    				}
    			}
    			result.add(head.next);
    		}
    		return result.toArray(new ListNode[0]);
    
        }
    }

## 这道题的收货 ##

实际上写的时候，我想到了用队列来辅助。但是要把每层构造成一个链表，这给我带来很大的麻烦，一时没相同，跑不通测试用例。所以链表的知识也应该再巩固一下。

关于队列，JDK给我们提供的队列里边， **ArrayBlockingQueue** 构造的时候**需要传入**一个队列的大小值。 而**LinkedBlockingQueue** 则不用。

想要取java中的最大值，可以使用 **Integer.MAX\_VALUE**

算法真的很痛苦~

痛苦的时候一般在提升吧！