leetcode429-N叉树的层序遍历

原题

给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。

例如,给定一个 3叉树 :

leetcode429-N叉树的层序遍历

返回其层序遍历:

[
     [1],
     [3,2,4],
     [5,6]
]

说明:
1. 树的深度不会超过 1000。
2. 树的节点总数不会超过 5000。

解法

思想

类似leetcode102-二叉树的层次遍历,通过DFS或BFS实现。

代码

迭代(BFS):

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        Queue<Node> 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()){
            Node node = queue.poll();
            if(node == null){
                if(cur.size()!=0) ans.add(cur);
                cur = new ArrayList<>();
            }else{
                cur.add(node.val);
                for(Node child:node.children){
                    if(child!=null) queue.offer(child);
                }
                //若队首为null说明这一层的节点的子节点已经全部加入队列了,需要加入一个null
                if(queue.peek()==null) queue.offer(null);
            }
        }
        return ans;
    }
}

递归(DFS):

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

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

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月20日 02:23
下一篇 2020年1月20日 20:39

相关推荐

  • leetcode1013-将数组分成和相等的三个部分

    原题 给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。 形式上,如果可以找出索引 i+1 < j 且满足 (A[0] +…

    算法 2020年3月11日
    0560
  • leetcode779-第K个语法符号

    原题 在第一行我们写上一个 0。接下来的每一行,将前一行中的0替换为01,1替换为10。 给定行数 N 和序数 K,返回第 N 行中第 K个字符。(K从1开始) 例子: 输入: N…

    算法 2020年1月22日
    0110
  • leetcode200-岛屿数量

    原题 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水…

    算法 2019年11月24日
    0150
  • leetcode707-设计链表

    原题 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用…

    算法 2019年12月14日
    0290
  • leetcode49-字母异位词分组

    原题 给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。 示例: 输入: ["eat", "tea", "tan", "ate", "nat",…

    算法 2019年12月25日
    0110
  • 海量数据-两种方法解决top k问题

    假如提供一百万个数据(甚至更大)的无序数组,如何从中获取最大的k个元素? 最容易想到的是先降序排序然后获取前k个元素,那假设我们用最常用的O(nlogn)级别的排序算法,要获取to…

    2020年4月4日
    0230
  • leetcode283-移动零

    原题 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说…

    算法 2019年11月23日
    0110
  • leetcode32-最长有效括号

    原题 给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。 示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2…

    算法 2020年6月12日
    0160
  • leetcode658-找到K个最接近的元素

    原题 给定一个排序好的数组,两个整数 k 和 x,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样,优先选择数值较…

    算法 2020年1月4日
    0120
  • leetcode116-填充每个节点的下一个右侧节点指针

    原题 给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下: struct Node {   int val;  &…

    2020年1月14日
    0530

发表回复

登录后才能评论