前往leetcode刷此题

解题思路

这道题其实还是蛮简单的，dfs 和 bfs都能解决。题目的大致意思是遍历一个二叉树，将其每层节点放入到一个二元数组中。
而且还要求是逐层遍历，从左至右访问所有节点。那在遍历的时候我们只需要考虑左右顺序以及层级就行了。

BFS

因为需要逐层遍历，所以我们需要将每一层的数据按序放入到队列中，然后将每层的节点按照从左至右的顺序放入到一个临时数组level中。

  1. 首先套用最基本的模板, 初始化队列并将根节点放入到队列中
queue = collections.deque()
        queue.append(root)
        res = []
  1. 遍历队列并创建一个临时数组level，将找到的节点放入到level中，然后继续往下层遍历，将节点的左右子节点放入到队列中继续遍历。
while queue:
       size = len(queue)
       level = []
       for _ in range(size):
          cur = queue.popleft()
          if not cur:
             continue
          level.append(cur.val)
          queue.append(cur.left)
          queue.append(cur.right)
       if level:
          res.append(level)
代码实现
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        queue = collections.deque()
        queue.append(root)
        res = []
        while queue:
            size = len(queue)
            level = []
            for _ in range(size):
                cur = queue.popleft()
                if not cur:
                    continue
                level.append(cur.val)
                queue.append(cur.left)
                queue.append(cur.right)
            if level:
                res.append(level)
        return res

复杂度分析

  • 时间复杂度: 每一个节点只操作一次 O(N)
  • 空间复杂度: 每一个节点不会重复放入到队列中 O(N)
DFS

用深度优先做这道题的话与以往不同的，深度优先没发确定当时遍历在哪一层，所以同广度优先一样需要用level来辅助。还需要注意先遍历左边再遍历右边。

代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

复杂度分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(N)