六六力扣刷题二叉树之层序遍历

时间：2022-10-30 17:59:05


前言

之前小六六一直觉得自己的算法比较菜，算是一个短板吧，以前刷题也还真是三天打鱼，两天晒网，刷几天，然后就慢慢的不坚持了，所以这次，借助平台的活动，打算慢慢的开始开刷，并且自己还会给刷的题总结下，谈谈自己的一些思考，和自己的思路等等，希望对小伙伴能有所帮助吧，也可以借此机会把自己短板补一补，希望自己能坚持下去呀

链表的合集

  • ​​六六力扣刷题哈希表之哈希理论​​
  • ​​六六力扣刷题哈希表之有效的字母异位词​​
  • ​​六六力扣刷题哈希表之两个数组的交集​​
  • ​​六六力扣刷题哈希表之快乐数​​
  • ​​六六力扣刷题哈希表之赎金信​​
  • ​​六六力扣刷题哈希表之三数之和​​

字符串

  • ​​六六力扣刷题字符串之反转字符串​​
  • ​​六六力扣刷题字符串之反转字符串2​​
  • ​​六六力扣刷题字符串之替换空格​​
  • ​​六六力扣刷题字符串之反转字符串中的单词​​
  • ​​六六力扣刷题字符串之找出字符串中第一个匹配项的下​​
  • ​​六六力扣刷题字符串之重复的子字符串​​

双指针

  • ​​六六力扣刷题双指针之移除元素​​
  • ​​六六力扣刷题双指针之删除链表的倒数第N个节点​​
  • ​​六六力扣刷题双指针之链表相交​​
  • ​​六六力扣刷题双指针之三数之和​​
  • ​​六六力扣刷题双指针之反转链表​​

搜索二叉树

  • ​​六六力扣刷题二叉树之基础​​
  • ​​六六力扣刷题二叉树之递归遍历​​
  • ​​六六力扣刷题二叉树之迭代遍历​​

题目

给你二叉树的根节点 ​​root​​ ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

六六力扣刷题二叉树之层序遍历

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

示例 2：

输入： root = [1]
输出： [[1]]

示例 3：

输入： root = []
输出： []

广度优先搜索

思路和算法

我们可以用广度优先搜索解决这个问题。

我们可以想到最朴素的方法是用一个二元组 (node, level) 来表示状态，它表示某个节点和它所在的层数，每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类，分类的时候我们可以利用哈希表，维护一个以 level 为键，对应节点值组成的数组为值，广度优先搜索结束以后按键 level 从小到大取出所有值，组成答案返回即可。

考虑如何优化空间开销：如何不用哈希映射，并且只用一个变量 node 表示状态，实现这个功能呢？

我们可以用一种巧妙的方法修改广度优先搜索：

首先根元素入队 当队列不为空的时候 求当前队列的长度 s_is i

依次从队列中取 s_is i 个元素进行拓展，然后进入下一次迭代

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++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);
                }
            }
            ret.add(level);
        }

        return ret;
    }
}

结束

  • 首先根节点入队，当队列非空时，重复如下两步操作。
  • 对头结点出队，并访问出对结点
  • 出队结点的左、右孩子依次入队。

好了，今天就到这了，大家继续加油！冲冲冲！我是小六六，三天打鱼，两天晒网！

标签：

相关文章