107.二叉树的层序遍历II

链接：107.二叉树的层序遍历II
难度：Medium
标签：树、广度优先搜索、二叉树
简介：给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。

题解 1 - java

• 编辑时间：2020-02-21
• 执行用时：2ms
• 内存消耗：39.1MB
• 编程语言：java
• 解法介绍：层序遍历，利用链表每次在头结点添加。

class Solution {
	LinkedList<List<Integer>> list = new LinkedList<List<Integer>>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root==null)return list;
        levelOrder(root, 0);
        return list;
    }
    public void levelOrder(TreeNode node,int level) {
    	if(list.size()==level)list.addFirst(new ArrayList<Integer>());
    	list.get(list.size()-level-1).add(node.val);
    	if(node.left!=null)levelOrder(node.left,1+ level);
    	if(node.right!=null)levelOrder(node.right,1+ level);
    }
}

题解 2 - typescript

• 编辑时间：2020-09-06
• 执行用时：76ms
• 内存消耗：39.8MB
• 编程语言：typescript
• 解法介绍：层序遍历。

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function levelOrderBottom(root: TreeNode | null): number[][] {
  if (root === null) return [];
  const ans: number[][] = [[root.val]];
  let size = 1;
  const queue = [root];
  while (queue.length !== 0) {
    const node = queue.shift()!;
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
    if (--size === 0) {
      size = queue.length;
      ans.push(queue.map(node => node.val));
    }
  }
  ans.pop();
  return ans.reverse();
}

题解 3 - python

• 编辑时间：2024-02-15
• 执行用时：44ms
• 内存消耗：16.62MB
• 编程语言：python
• 解法介绍：bfs。

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        q = deque() 
        q.append(root)
        size = 1
        ans = [[root.val]]
        while q:
            node = q.popleft()
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
            size -= 1
            if size == 0:
                size = len(q)
                if q: ans.append([node.val for node in q])
        return ans[::-1]