特定深度节点链表
难度:
标签:
题目描述
Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you'll have D linked lists). Return a array containing all the linked lists.
Example:
Input: [1,2,3,4,5,null,7,8]
1
/ \
2 3
/ \ \
4 5 7
/
8
Output: [[1],[2,3],[4,5,7],[8]]
代码结果
运行时间: 21 ms, 内存: 16.0 MB
/*
* 思路：
* 1. 使用递归方法遍历二叉树的每一层。
* 2. 对于每一层，创建一个新的链表，并将该层的所有节点添加到链表中。
* 3. 使用Stream API进行处理和收集结果。
*/
import java.util.*;
import java.util.stream.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List<List<Integer>> listOfDepth(TreeNode tree) {
Map<Integer, List<Integer>> levelMap = new HashMap<>();
traverse(tree, 0, levelMap);
return levelMap.values().stream().collect(Collectors.toList());
}
private void traverse(TreeNode node, int depth, Map<Integer, List<Integer>> levelMap) {
if (node == null) return;
levelMap.computeIfAbsent(depth, k -> new ArrayList<>()).add(node.val);
traverse(node.left, depth + 1, levelMap);
traverse(node.right, depth + 1, levelMap);
}
}解释
方法:
该题解采用层次遍历（广度优先遍历）的方法遍历二叉树的每一层。在遍历过程中，使用一个队列stack来存储当前层的所有节点。对于每一层，将节点从队列中取出，并将其子节点（左和右，如果存在）添加到队列中，以便于后续层的遍历。同时，将当前层的节点转换为链表。这一转换通过辅助函数tree2list完成，该函数接受当前层的节点数组，创建一个新的链表头节点，然后遍历数组中的每个节点，将其添加到链表中。最终，这个链表被添加到结果列表中。整个过程重复，直到队列为空，即所有层都被处理完毕。
时间复杂度:
O(N)
空间复杂度:
O(N)
代码细节讲解
🦆
在函数`tree2list`中，如果当前层节点数组为空，函数直接返回。这种情况在何种场景下会发生？
▷🦆
在广度优先遍历中使用的队列`stack`为何使用列表实现？使用列表进行pop(0)操作的时间复杂性是多少？是否有更高效的数据结构选择？
▷🦆
题解中对于每一个层级的节点都创建了一个链表，并将其存储在结果数组中。这种数据结构的选择（即使用链表而不是简单数组）的理由是什么？
▷