107_二叉树的层序遍历_II

类型：树

• 107. 二叉树的层序遍历 II 💛

  https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/

  ❓ 给定一个二叉树，返回其节点值自底向上的层序遍历。

  💡 BFS

  在遍历完一层节点之后，将存储该层节点值的列表添加到结果列表的头部。

  class Solution:
      def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
          if not root:
              return []
          queue = [root]
          output = []
          while queue:
              tempQueue = []
              levelOuput = []
              for node in queue:
                  levelOuput.append(node.val)
                  if node.left:
                      tempQueue.append(node.left)
                  if node.right:
                      tempQueue.append(node.right)
              queue = tempQueue
              output.insert(0, levelOuput)
          return output

  时间复杂度：O(n)，空间复杂度：O(n)