难度: Medium
给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。
示例：
输入：[1,2,3,4,5,null,7,8]
1
/ \
2 3
/ \ \
4 5 7
/
8
输出：[[1],[2,3],[4,5,7],[8]]
Submission
运行时间: 21 ms
内存: 16.0 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def listOfDepth(self, tree: TreeNode) -> List[ListNode]:
def tree2list(nodes):
if not len(nodes):
return
head = ListNode(nodes[0].val)
cur = head
for n in nodes[1:]:
cur.next = ListNode(n.val)
cur = cur.next
return head
ans = []
stack = [tree]
while stack:
ans.append([])
count = len(stack)
while count:
count -= 1
node = stack.pop(0)
ans[-1].append(node)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
ans[-1] = tree2list(ans[-1])
return ans
Explain
该题解采用层次遍历（广度优先遍历）的方法遍历二叉树的每一层。在遍历过程中，使用一个队列stack来存储当前层的所有节点。对于每一层，将节点从队列中取出，并将其子节点（左和右，如果存在）添加到队列中，以便于后续层的遍历。同时，将当前层的节点转换为链表。这一转换通过辅助函数tree2list完成，该函数接受当前层的节点数组，创建一个新的链表头节点，然后遍历数组中的每个节点，将其添加到链表中。最终，这个链表被添加到结果列表中。整个过程重复，直到队列为空，即所有层都被处理完毕。
时间复杂度: O(N)
空间复杂度: O(N)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def listOfDepth(self, tree: TreeNode) -> List[ListNode]:
def tree2list(nodes):
# Check if the list of nodes is empty
if not len(nodes):
return
# Initialize the head of the list
head = ListNode(nodes[0].val)
cur = head
# Convert each tree node to a linked list node
for n in nodes[1:]:
cur.next = ListNode(n.val)
cur = cur.next
return head
ans = []
stack = [tree]
while stack:
ans.append([])
count = len(stack)
# Process each node in the current level
while count:
count -= 1
node = stack.pop(0)
ans[-1].append(node)
# Add children to the stack for next level
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
# Convert current level nodes into a linked list
ans[-1] = tree2list(ans[-1])
return ans
Explore
这种情况在二叉树中的某一层不存在任何节点时发生，例如，所有节点都在左子树或右子树中，而另一侧子树完全为空。此时，虽然算法尝试访问这一层，但因为实际上这一层没有节点，所以传入`tree2list`的节点数组为空，函数因此直接返回。
在该题解中，队列是用Python的列表实现的。使用列表的`pop(0)`操作来移除队列的第一个元素，这是一个时间复杂度为O(n)的操作，因为它需要移动列表中的所有其他元素来填补被移除元素留下的空位。一个更高效的选择是使用`collections.deque`，它支持O(1)时间复杂度的`append`和`popleft`操作，使得队列操作更加高效。
使用链表而不是数组的主要理由是，链表在动态数据操作中更加灵活。在构建每层节点的链表时，由于节点数量不确定，链表允许我们以常数时间复杂度O(1)添加新节点（在链表尾部），这比可能需要扩容的数组更优。此外，题目可能是为了测试链表操作的实现，因此选择了链表来存储每层的节点。