Leetcode 107 二叉树的层序遍历II // 洛七的摸鱼池塘

107.二叉树的层序遍历II

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

示例 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

解答

本题的难度是 Medium.

一开始写的很抽象, 先创建一个 HashMap, 然后记录最大深度, 然后再倒序插入到 result 里.

代码如下:

class Solution {
    private int maxDepth = -1;
    HashMap<Integer, ArrayList<Integer>> hashMap = new HashMap();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        levelOrder(root, 0);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = maxDepth; i >= 0 ; i--) {
            result.add(hashMap.get(i));
        }
        return result;
    }

    private void levelOrder(TreeNode node, int depth){
        if (node == null){return;}
        if (depth > maxDepth) { maxDepth = depth;}
        if (!hashMap.containsKey(depth)){
            hashMap.put(depth, new ArrayList<>());
        }
        ArrayList<Integer> list = hashMap.get(depth);
        list.add(node.val);
        hashMap.put(depth, list);
        levelOrder(node.left, depth+1);
        levelOrder(node.right, depth+1);
    }
}

1ms, 击败 92.43% 的提交.

然后发现根本不用这样做, 本质还是层序遍历, 把层序遍历倒一下就好了, 于是改了一下.

class Solution {
    List<List<Integer>> lists = new ArrayList<>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {

        ceng(0, root);
        Collections.reverse(lists);
        return lists;
    }

    private void ceng(int cengIndex, TreeNode node){
        if(node == null ){return ;}
        if(lists.size() < (1+cengIndex)){
            lists.add(new ArrayList<>());
        }
        lists.get(cengIndex).add(node.val);
        ceng(cengIndex+1, node.left);
        ceng(cengIndex+1, node.right);
    }
}

好好好, 0ms, 击败 100% 的提交.