面试题 04.03. 特定深度节点链表
给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。
示例：
输入：[1,2,3,4,5,null,7,8]
1
/ \
2 3
/ \ \
4 5 7
/
8
输出：[[1],[2,3],[4,5,7],[8]]
原站题解
python3 解法, 执行用时: 44 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-11 13:49:32
# 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]:
'''
广度优先搜索
'''
res = []
q = collections.deque()
q.append(tree)
while q:
head = ListNode(-1)
cur = head
for i in range(len(q)):
node = q.popleft()
cur.next = ListNode(node.val)
cur = cur.next
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(head.next)
return res
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2022-11-11 13:48:11
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func listOfDepth(tree *TreeNode) []*ListNode {
queue := []*TreeNode{tree}
ans := []*ListNode{}
for len(queue) > 0 {
size := len(queue)
list := &ListNode{}
curr := list
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
curr.Next = &ListNode{Val:node.Val}
curr = curr.Next
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil{
queue = append(queue, node.Right)
}
}
ans = append(ans, list.Next)
}
return ans
}
python3 解法, 执行用时: 40 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-11 13:43:17
# 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, root: TreeNode) -> List[ListNode]:
'''
层级遍历
'''
ans = []
def dfs(node: TreeNode, level: int):
if not node: return None
if len(ans) == level:
ans.append(ListNode(node.val))
else:
head = ListNode(node.val)
head.next = ans[level]
ans[level] = head
dfs(node.right, level + 1)
dfs(node.left, level + 1)
dfs(root, 0)
return ans