1, 题目

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

  1.     3
  2.   / \
  3.  9  20
  4.    /  \
  5.   15   7

返回其自底向上的层次遍历为：

  1. [
  2.  [15,7],
  3.  [9,20],
  4.  [3]
  5. ]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2, 算法

  1. 层次遍历应该是最简单的算法了
  2. 记录每一层的深度,一个队列,一次循环
  1. object Solution {
  2.     def levelOrderBottom(root: TreeNode): List[List[Int]] = {
  3.         val queue = scala.collection.mutable.Queue[(TreeNode, Int)]()
  4.         if (root != null) {
  5.             queue.enqueue((root, 1))
  6.         }
  7.         var current = 1
  8.         val stack = scala.collection.mutable.Stack[List[Int]]()
  9.         val list = scala.collection.mutable.ListBuffer[Int]()
  10.         while (queue.nonEmpty) {
  11.             val node = queue.dequeue()
  12.             if (node._1.left != null) {
  13.                 queue.enqueue((node._1.left, node._2 + 1))
  14.             }
  15.             if (node._1.right != null) {
  16.                 queue.enqueue((node._1.right, node._2 + 1))
  17.             }
  19.             if (current == node._2) {
  20.                 list.append(node._1.value)
  21.             } else {
  22.                 stack.push(list.toList)
  23.                 list.clear()
  24.                 list.append(node._1.value)
  25.                 current = node._2
  26.             }
  27.         }
  28.         if (list.nonEmpty) {
  29.             stack.push(list.toList)
  30.         }
  31.         stack.toList
  32.     }
  33. }
  1. class Solution:
  2.     def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
  3.         import queue
  4.         q = queue.Queue()
  5.         if root:
  6.             q.put((root, 1))
  7.         current = 1
  8.         arr = []
  9.         l = []
  10.         while not q.empty():
  11.             node, level = q.get()
  12.             if node.left:
  13.                 q.put((node.left, level + 1))
  14.             if node.right:
  15.                 q.put((node.right, level + 1))
  16.             if current == level:
  17.                 l.append(node.val)
  18.             else:
  19.                 arr.append(l.copy())
  20.                 l.clear()
  21.                 l.append(node.val)
  22.                 current = level
  23.         if l:
  24.             arr.append(l.copy())
  25.         return list(reversed(arr))