本文共 1372 字，大约阅读时间需要 4 分钟。

思路一、BFS广度优先搜索

计算每层的结点数，在将它们逐个弹出加入层列表，并将其子结点加入队列

• 1、通过迭代形式将每层结点加入队列，
• 2、通过计算每层结点的数量(上层结点都从队列中弹出，而下层结点尚未加入队列，就可计算当层结点的数量。)
• 3、遍历当层结点，将这些结点放入层列表，并将它们的子结点加入队列，作为下一层待操作的结点

代码实现

class Solution:    def levelOrder(self, root: TreeNode) -> List[List[int]]:        if root == None: return []                result = []        queue = collections.deque()        queue.append(root)                # visited = set(root)                while queue:            current_level = []            level_size = len(queue)                        for _ in range(level_size):                node = queue.popleft()                current_level.append(node.val)                if node.left: queue.append(node.left)                if node.right: queue.append(node.right)                            result.append(current_level)                return result

时间复杂度为O(N)

思路二、DFS深度优先搜索

带着当前层级数递归，层级数是当前层子列表的索引，每经过一个结点就将其加入当前层子列表

class Solution:    def levelOrder(self, root: TreeNode) -> List[List[int]]:        if root == None: return []        self.result = []        self._DSF(root, 0)        return self.result        def _DSF(self, node, level):        if not node: return                if len(self.result) < level + 1:            self.result.append([])                self.result[level].append(node.val)                self._DSF(node.left, level + 1)        self._DSF(node.right, level + 1)

时间复杂度为O(N)

转载地址：http://mghrb.baihongyu.com/