☆打卡算法☆LeetCode 107、二叉树的层序遍历 II 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定二叉树根节点，返回节点值自底向上的层序遍历。”

题目链接：

来源：力扣（LeetCode）

链接：107. 二叉树的层序遍历 II - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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

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

示例 2：
输入： root = [1]
输出： [[1]]

二、解题

1、思路分析

这道题和102题二叉树的层序遍历类似，不同的地方在于102题要求从上到下输出每一层的节点值。

这一题是从下到上输出每一层的节点值。

虽然说输出顺序不同，但是思路是相同的，都可以使用广度优先搜索记性层次遍历。

从根节点开始搜索，每次遍历同一层的全部节点，使用列表存储改层的节点值。

在遍历完一层节点之后，将存储该层节点值的列表添加到结果列表的头部。

2、代码实现

代码参考：

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
        if (root == null) {
            return levelOrder;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                TreeNode left = node.left, right = node.right;
                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
            }
            levelOrder.add(0, level);
        }
        return levelOrder;
    }
}

3、时间复杂度

时间复杂度 ： O(n)

其中n是树中的节点个数。每个节点访问一次，结果列表使用链表的结构，在结构列表头部添加一层节点值的列表的时间复杂度为O(1)，因此总时间复杂度为O(n)。

空间复杂度： O(n)

其中n是树中的节点个数。

三、总结

为了降低在结果列表头部添加一层节点值的列表的时间复杂度，结果列表可以使用链表的结构。

在代码中，需要返回List类型的数据，可以使用链表实现。