Leetcode107. 二叉树的层序遍历 II

题目描述

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

思路分析

1. 二叉树的层序遍历，及一层一层的遍历二叉树，将每一层遍历的结果存储到集合中
2. 因此需要维护一个队列保存每层的节点，然后遍历这些节点，取值并将它的子节点再记录到队列中
3. 因为是自底向上的层序遍历，因此要将每层遍历的节点值添加到集合的首部
4. 详解代码见下

源码及分析

 /**
     * @param root 根节点
     * @return 返回层序遍历的结果
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        //定义集合保存结果，注意添加结果时要添加到集合的头部
        LinkedList<List<Integer>> res = new LinkedList<>();
        //数据校验
        if (root == null) {
            return res;
        }
        //维护一个队列保存每一层的节点
        Queue<TreeNode> nodes = new LinkedList<>();
        nodes.offer(root);
        while (!nodes.isEmpty()){
            //创建集合保存每一层的节点值
            ArrayList<Integer> level = new ArrayList<>();
            //记录每一层的节点数，用于遍历
            int size = nodes.size();
            //遍历每一层的节点，记录节点值，并记录下一层子节点
            for (int i = 0; i < size; i++) {
                TreeNode node = nodes.poll();
                level.add(node.val);
                if (node.left != null){
                    nodes.offer(node.left);
                }
                if (node.right != null){
                    nodes.offer(node.right);
                }
            }
            //将每一层结果倒序添加
            res.add(0,level);
        }
        return res;
    }