做网站唐山,做一款手机app大概多少钱,网站建设 全包 制作,网页设计与制作作业成品429. N 叉树的层序遍历
给定一个 N 叉树#xff0c;返回其节点值的层序遍历。#xff08;即从左到右#xff0c;逐层遍历#xff09;。
树的序列化输入是用层序遍历#xff0c;每组子节点都由 null 值分隔#xff08;参见示例#xff09;。
示例 1#xff1a;输入返回其节点值的层序遍历。即从左到右逐层遍历。
树的序列化输入是用层序遍历每组子节点都由 null 值分隔参见示例。
示例 1输入root [1,null,3,2,4,null,5,6]
输出[[1],[3,2,4],[5,6]]示例 2输入root [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]提示
树的高度不会超过 1000
树的节点总数在 [0, 10^4] 之间题解 主要思路就是常规BFS只不过每次从队列拿元素的时候一次将一层的节点全部拿出再将这些节点下层的children都同时入队即可。这样会造成最后多一次入队出队所以最后加上一次判空操作即可 代码
/*
// Definition for a Node.
class Node {public int val;public ListNode children;public Node() {}public Node(int _val) {val _val;}public Node(int _val, ListNode _children) {val _val;children _children;}
};
*/class Solution {public ListListInteger levelOrder(Node root) {QueueNode queue new LinkedList();ListListInteger res new ArrayList();if(root null){return res;}queue.offer(root);ListInteger list new ArrayList();list.add(root.val);res.add(list);while(!queue.isEmpty()){// 队列想边拿边加时则利用长度字段想只拿不加可以用队列判空最后队列再加ListListNode tmpList new ArrayList();while(!queue.isEmpty()){// 出队// 将同层的节点一次拿出Node tmpQueueOne queue.poll();if(tmpQueueOne.children ! null)tmpList.add(tmpQueueOne.children);}if(tmpList null || tmpList.size() 0)continue;int tmpLen tmpList.size();ListInteger tmpResOfOne new ArrayList();for(int i0;itmpLen;i){if(tmpList.get(i) ! null){for(int j0;jtmpList.get(i).size();j){tmpResOfOne.add(tmpList.get(i).get(j).val);// 入队// 将本层下层的孩子全部同时入队queue.offer(tmpList.get(i).get(j));}}}if(tmpResOfOne null || tmpResOfOne.size() 0)continue;res.add(tmpResOfOne);}return res;}
}
