上海建设局网站首页/竞价托管信息

今天继续做关于二叉树层序遍历的相关题目，一共有三道题，思路都借鉴于最基础的二叉树的层序遍历。

LeetCode429.N叉树的层序遍历

这道题不再是二叉树了，变成了N叉树，也就是该树每一个节点的子节点数量不确定，可能为2，可能为1，也可能为3等等。要求也是需要从左到右层序遍历，和二叉树的层序遍历类似，需要改动的地方有，每一个节点出队时，其叶子节点全部存于一个列表中，将这个列表中的全部元素入队即可，不再是将二叉树仅有的两个子节点：左子节点，右子节点入队。

	public static List<List<Integer>> levelOrder(Node root){List<List<Integer>> list=new ArrayList<>();Queue<Node> queue=new LinkedList<>();if (root==null){return list;}else {queue.offer(root);}Node node=root;while (!queue.isEmpty()){int size=queue.size();List<Integer> lst = new ArrayList<>();for (int i = 0; i < size; i++) {node=queue.poll();if (node.children!=null) {for (int j = 0; j < node.children.size(); j++) {queue.offer(node.children.get(j));}}lst.add(node.val);}list.add(lst);}return list;}

LeetCode515.在每个树行中找最大值

这道题先层序遍历，可以将每一层的所有元素存入数组，然后比较数组中的所有元素，选出最大值，即为二叉树该层的最大值，如此循环，将二叉树的所有层都遍历完成。

	public static int researchMax(List<Integer> list){int max=list.get(0);for (int i = 0; i < list.size(); i++) {if (max<list.get(i)){max=list.get(i);}}return max;}public List<Integer> largestValues(TreeNode root){List<Integer> list=new ArrayList<>();Queue<TreeNode> queue=new LinkedList<>();if (root==null){return list;}else {queue.offer(root);}TreeNode node;while (!queue.isEmpty()){List<Integer> lst = new ArrayList<>();int size= queue.size();for (int i = 0; i < size; i++) {node=queue.poll();if (node.left!=null){queue.offer(node.left);}if (node.right!=null){queue.offer(node.right);}lst.add(node.val);}list.add(researchMax(lst));}return list;}

LeetCode116.填充每个节点的下一个右侧节点指针

层序遍历，将每一个出队后的节点的next指针指向这时队列的peak。这里一定需要一个计数器，每次进入循环时，记录当前的队列长度，也就是当前树行的节点个数，如果遍历到最后一个节点时，后面没有节点了，这时就需要将next指针指向null值。

	public static Node connect(Node root){Queue<Node> queue=new LinkedList<>();if (root==null){return null;}else {queue.offer(root);}Node node;while (!queue.isEmpty()){int size= queue.size();for (int i = 0; i < size; i++) {node=queue.poll();if (i==size-1){node.next=null;}else {node.next=queue.peek();}if (node.left!=null){queue.offer(node.left);}if (node.right!=null){queue.offer(node.right);}}}return root;}