【LeetCode】107.二叉树的层序遍历II

1.问题

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1：

"图1"

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

2.解题思路

其实与【LeetCode】102.二叉树的层序遍历广度优先的思路没啥大的区别，从结果来看，就是结果集逆序输出，只要我们在遍历每层完成后，将临时结果集按照头插法插入结果集即可。可以利用List.add(index,value)的方法完成头插法。

3.代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        //分层遍历，利用队列思想，头插法
        if(null == root){
            return new ArrayList();
        }
        //结果集
        List<List<Integer>> res=new ArrayList();
        //每层的结果集
        List<Integer> tempList=new ArrayList();
        List<TreeNode> temp=new ArrayList<TreeNode>();
        //根节点入队
        temp.add(root);
        temp.add(null);
        TreeNode node;
        while(!temp.isEmpty()){
            node=temp.remove(0);
            if(null != node){
                tempList.add(node.val);
                if(null!=node.left){
                    temp.add(node.left);
                }
                if(null!=node.right){
                    temp.add(node.right);
                }
            } 
            //本层已遍历完毕
            else if(!tempList.isEmpty()){
                //头插法（与102不同的地方）
                res.add(0, tempList);
                tempList=new ArrayList();
                temp.add(null);
            }
        }
        return res;
    }
}