LeetCode 107. 二叉树的层序遍历 II Java实现

题目要求

给定二叉树，返回其节点值自底向上的层序遍历，即从叶子层到根层。

例如：

    3
   / \
  9  20
     / \
    15  7

返回：

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

方法一：BFS + 头插（推荐）

使用队列进行正常层序遍历，每层结果用 LinkedList.addFirst() 插入到结果头部，即可实现自底向上。

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> res = new LinkedList<>();
        if (root == null) return res;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            // 头插，实现自底向上
            res.addFirst(level);
        }

        return res;
    }
}

方法二：BFS + 最后反转

正常层序遍历，把每层依次加入结果，最后整体反转。

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            res.add(level);
        }

        Collections.reverse(res);
        return res;
    }
}

方法三：DFS 递归

深度优先遍历，记录每个节点所在层数，最后反转结果。

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, 0, res);
        Collections.reverse(res);
        return res;
    }

    private void dfs(TreeNode node, int depth, List<List<Integer>> res) {
        if (node == null) return;

        // 新的一层
        if (depth == res.size()) {
            res.add(new ArrayList<>());
        }

        res.get(depth).add(node.val);

        dfs(node.left, depth + 1, res);
        dfs(node.right, depth + 1, res);
    }
}

复杂度分析

方法 时间复杂度 空间复杂度
BFS + 头插 O(n) O(n)
BFS + 反转 O(n) O(n)
DFS O(n) O(h)，h 为树高

其中 n 为节点总数。BFS 队列最多存一层的节点数，最坏 O(n)；DFS 递归栈深度为树高。

推荐

面试中推荐 方法一（BFS + 头插），逻辑清晰，无需最后反转，且直接得到自底向上的结果。