剑指 Offer 32 - Ⅳ. 从下到上打印二叉树 Ⅳ

题目：给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如：
给定二叉树 [3,9,20,null,null,15,7],

• 3
• / \
• 9 20
• / \
• 15 7

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

• [
• [15,7],
• [9,20],
• [3]
• ]

  解法1：BFS，使用队列，时间复杂度o(n)，空间复杂度o(n)

1. 使用一个队列，先加入当前root，两层循环，判断条件都是队列是否为null，大循环判断每一层，小循环判断每一层内的每个节点
2. 在每一层中用一个list依次从左到右加入节点，即取出当前节点加入list，然后按照左右子节点的顺序依次入队
3. 依次取出当前节点，然后分别把它的左右节点加入到队列
4. 每层结束时，把结果都插入到结果集的头部即可（这样从上到下就反过来成为从左到右了）

   import java.util.*;
   class Solution {
    LinkedList<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root == null)
            return res;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        while(!deque.isEmpty()){
            int sz = deque.size();
            List<Integer> list = new LinkedList<>();
            for(int i = 0 ; i < sz ;i++){
                TreeNode node = deque.poll();
                list.add(node.val);
                if(node.left != null)
                    deque.add(node.left);
                if(node.right != null)
                    deque.add(node.right);
            }
            res.addFirst(list);
        }
        return res;
    }
   }