leetcode102-二叉树的层次遍历

原题

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果:

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

解法

思想

  1. 迭代,广度优先搜索,但需要记录元素是哪一层的。
  2. 递归,深度优先搜索,将元素加进每层对应的List中

代码

迭代:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        if(root == null) return new ArrayList<List<Integer>>();
        queue.offer(root);
        queue.offer(null);//以null作为每层结束的标志符
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node == null){
                if(cur.size()!=0) ans.add(cur);
                cur = new ArrayList<>();
            }else{
                cur.add(node.val);
                if(node.left!=null) queue.offer(node.left);
                if(node.right!=null) queue.offer(node.right);
                //若队首为null说明这一层的节点的子节点已经全部加入队列了,需要加入一个null
                if(queue.peek()==null) queue.offer(null);
            }
        }
        return ans;
    }
}

递归:

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null)
            return ans;
        DFS(root,0);
        return ans;
    }
    public void DFS(TreeNode root,int level){
        if(ans.size()==level)
            ans.add(new ArrayList<Integer>());
        ans.get(level).add(root.val);
        if(root.left!=null)
            DFS(root.left,level+1);
        if(root.right!=null)
            DFS(root.right,level+1);
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode102-%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e5%b1%82%e6%ac%a1%e9%81%8d%e5%8e%86/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月10日 22:55
下一篇 2020年1月11日

相关推荐

  • leetcode110-平衡二叉树

    原题 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1:  给定二叉树 […

    算法 2020年1月17日
    0170
  • leetcode771-宝石与石头

    原题 给定字符串J 代表石头中宝石的类型,和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。 J 中的字母不重复,J …

    算法 2019年12月26日
    0350
  • leetcode706-设计哈希映射

    原题 不使用任何内建的哈希表库设计一个哈希映射 具体地说,你的设计应该包含以下的功能 put(key, value):向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在,更…

    算法 2019年12月18日
    0110
  • leetcode347-前K个高频元素

    原题 给定一个非空的整数数组,返回其中出现频率前 k 高的元素。 示例1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例2: 输入: n…

    算法 2019年12月28日
    0140
  • 剑指offer44-数字序列中某一位的数字

    原题(来源Leetcode) 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从下标0开始计数)是5,第13位是1,第19位…

    算法 2020年6月15日
    02870
  • 十大排序算法与Java实现

    本文参考资源: https://github.com/iTimeTraveler/SortAlgorithms 十大经典排序算法 - 冰狼爱魔 - 博客园 十大经典排序算法总结(J…

    2020年3月11日
    0770
  • leetcode1095-山脉数组中查找目标值

    原题 (这是一个 交互式问题 ) 给你一个 山脉数组 mountainArr,请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 in…

    算法 2020年4月29日
    0110
  • leetcode350-两个数组的交集II

    原题 给定两个数组,编写一个函数来计算它们的交集。 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 示例2: 输入: nums1 = …

    算法 2019年12月23日
    0380
  • leetcode100-相同的树

    原题 给定两个二叉树,编写一个函数来检验它们是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: 输入: 1 1 / \ / \ 2 3 2 …

    算法 2020年5月7日
    0180
  • 剑指offer04-二维数组中的查找

    原题(来源Leetcode) 在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个…

    算法 2020年4月4日
    0130

发表回复

登录后才能评论