美文网首页
11.二叉树习题

11.二叉树习题

作者: 学海一乌鸦 | 来源:发表于2020-06-08 23:38 被阅读0次

102. 二叉树的层序遍历

在每一层遍历开始前,先记录队列中的结点数量 nn(也就是这一层的结点数量),然后一口气处理完这一层的 n个结点。
最牛B的在于一开始要先计算出来队列的长度: int n=queue.size();
空间复杂度:节点最多不超过n个,最多的为最后一层的叶子节点n/2,故空间复杂度为O(n)
时间复杂度:每个节点进出各一次,所以总体的时间复杂度为O(n)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        if(root==null){
            return list;
        }
         Queue<TreeNode> queue=new ArrayDeque<>();
        queue.add(root);
        while(!queue.isEmpty()){
            //一开始预先去queue的大小,后面再加元素也就不用担心了!!!
            int n=queue.size();
            List<Integer> innerList=new ArrayList<>();
            for(int i=0;i<n;i++){
                TreeNode node=queue.poll();
                innerList.add(node.val);
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            list.add(innerList);
        }
        return list;
    }
}

相关文章

  • 11.二叉树习题

    102. 二叉树的层序遍历 在每一层遍历开始前,先记录队列中的结点数量 nn(也就是这一层的结点数量),然后一口气...

  • 平衡二叉树的基本操作

    平衡二叉树定义及操作原理 C++简单实现 涉及练习题目:平衡二叉树的基本操作

  • 算法与数据结构

    二叉树 1. 二叉树打印练习题 有一棵二叉树,请设计一个算法,按照层次打印这棵二叉树。给定二叉树的根结点root,...

  • 226. Invert Binary Tree

    题意:翻转二叉树 思路:后根遍历,很好的练习题; 练习指数:5

  • 二叉树算法习题

    学习了二叉树的概念,针对学习结果做一些习题。 某二叉树中有n个度为2的节点,则该二叉树的叶子节点数为?解析:二叉树...

  • 数据结构与算法学习-二叉查找树

    之前整理了两篇关于二叉树的文章: 征战二叉树-第一站 征战二叉树-第二站 这两篇都是基于二叉树,以及一些练习题,本...

  • 二叉树 for iOS (Swift篇)

    学习了二叉树的概念及二叉树算法习题后, 结合学习的知识通过代码实现一些功能。 二叉树说白了是考验程序员的递归思维,...

  • 2019-09-23 算法学习笔记一

    1.LeetCode 对应习题 1.102 二叉树的层次遍历(1)BFS 广度优先搜索a.level => que...

  • 11.二叉树

    1.树的定义 1.1与节点相关的概念 节点的高度:该节点到叶子节点的最长路径(边的数量)节点的深度:根节点到该节点...

  • JavaScript数据结构与算法-二叉树

    前言: 之前做百度前端练习题时,遇到二叉树遍历的问题,由于不了解二叉树这种数据机构,自己只好学习一番并且总结如下。...

网友评论

      本文标题:11.二叉树习题

      本文链接:https://www.haomeiwen.com/subject/tpzlzhtx.html