二叉树自底向上的层次遍历

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

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

    3
   / \
  9  20
    /  \
   15   7
返回其自底向上的层次遍历为：

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

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

想出来的方法不太聪明的样子，2ms效率很低

public static List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> list = new ArrayList<>();

    Map<Integer, List<Integer>> map = new TreeMap<Integer, List<Integer>>(
            new Comparator<Integer>() {
                public int compare(Integer obj1, Integer obj2) {
                    // 降序排序
                    return obj2.compareTo(obj1);
                }
            });

    Integer val = layerTrace(root, 0, map);
    if (val != null) {
        if (map.containsKey(0)) {
            map.get(0).add(val);
        } else {

            map.put(0, Arrays.asList(val));
        }
    }


    for(Map.Entry set:map.entrySet()){
        list.add((List<Integer>) set.getValue());
    }


    return list;
}

public static Integer layerTrace(TreeNode root, int depth, Map<Integer, List<Integer>> map) {
    if (null != root) {
        if (root.left == null && root.right == null) {
            return root.val;
        }
        depth=depth+1;
        Integer left = layerTrace(root.left, depth, map);
        Integer right = layerTrace(root.right, depth, map);

        if (left != null) {
            if (map.containsKey(depth)) {
                map.get(depth).add(left);
            } else {
                List<Integer> list=new ArrayList<>();
                list.add(left);
                map.put(depth, list);
            }
        }

        if (right != null) {
            if (map.containsKey(depth)) {
                map.get(depth).add(right);
            } else {
                List<Integer> list=new ArrayList<>();
                list.add(right);
                map.put(depth, list);
            }
        }

        return root.val;
    } else {
        return null;
    }
}

大佬的写法，1ms效率比较高

public static List<List<Integer>> levelOrderBottom(TreeNode root) {
    LinkedList<List<Integer>> result = new LinkedList<>();
    if (root == null)
        return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        List<Integer> oneLevel = new ArrayList<>();
        // 每次都取出一层的所有数据
        int count = queue.size();
        for (int i = 0; i < count; i++) {
            TreeNode node = queue.poll();//每次把队列中最前面的拿出来
            oneLevel.add(node.val);
            if (node.left != null)
                queue.add(node.left);//将左子树入队
            if (node.right != null)
                queue.add(node.right);//将右子树入队
        }
        // 每次都往队头塞，最后添加进去的最先拿出来（有点像栈了）
        result.addFirst(oneLevel);
    }
    return result;
}

赏

谢谢你请我吃糖果

微信