程序员面试金典 - 面试题 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]]

题目思考

1. 如何依次处理同一深度的节点?

解决方案

思路

• 根据题目描述, 很直观的想法就是利用 BFS, 依次处理每一层的节点
• 在处理当前层时, 先新建一个哨兵节点, 其 next 即为该层链表头节点, 这样可以简化逻辑, 在连接链表时无需判断当前层的头节点是否为空
• 然后维护当前链表的末尾节点, 每次处理一个树节点时, 都新建一个链表节点, 并将当前末尾节点的 next 指向它
• 最后需要将树节点的非空左右子节点加入队列, 也即经典的 BFS 部分了
• 下面代码有详细的注释, 大家可以结合起来理解

复杂度

• 时间复杂度 O(N): 每个节点只需要遍历一遍
• 空间复杂度 O(N): 需要一个队列存所有节点

代码

class Solution:
    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:
        # 记录每层节点的BFS
        if not tree:
            return []
        res = []
        q = [tree]
        while q:
            curlen = len(q)
            # dummy是当前层链表的哨兵节点, 即头节点的前一个节点
            dummy = ListNode(0)
            # tail是当前层链表的末尾节点
            tail = dummy
            # 注意循环范围只能到curlen, 不能在当前层处理下一层的节点
            for treeNode in q[:curlen]:
                # 将新的链表节点连接到当前链表中
                tail.next = ListNode(treeNode.val)
                # 更新链表末尾
                tail = tail.next
                # 将左右子节点加入队列
                if treeNode.left:
                    q.append(treeNode.left)
                if treeNode.right:
                    q.append(treeNode.right)
            # dummy.next即为当前层链表的头节点
            res.append(dummy.next)
            # 移除当前层的节点, 准备处理下一层
            q = q[curlen:]
        return res

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊