网站如何加速,移动网站开发百度百科,重庆seo和网络推广,青岛建筑网今天继续做关于二叉树层序遍历的相关题目#xff0c;一共有三道题#xff0c;思路都借鉴于最基础的二叉树的层序遍历。
LeetCode429.N叉树的层序遍历 这道题不再是二叉树了#xff0c;变成了N叉树#xff0c;也就是该树每一个节点的子节点数量不确定#xff0c;可能为2一共有三道题思路都借鉴于最基础的二叉树的层序遍历。
LeetCode429.N叉树的层序遍历 这道题不再是二叉树了变成了N叉树也就是该树每一个节点的子节点数量不确定可能为2可能为1也可能为3等等。要求也是需要从左到右层序遍历和二叉树的层序遍历类似需要改动的地方有每一个节点出队时其叶子节点全部存于一个列表中将这个列表中的全部元素入队即可不再是将二叉树仅有的两个子节点左子节点右子节点入队。 public static ListListInteger levelOrder(Node root){ListListInteger listnew ArrayList();QueueNode queuenew LinkedList();if (rootnull){return list;}else {queue.offer(root);}Node noderoot;while (!queue.isEmpty()){int sizequeue.size();ListInteger lst new ArrayList();for (int i 0; i size; i) {nodequeue.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(ListInteger list){int maxlist.get(0);for (int i 0; i list.size(); i) {if (maxlist.get(i)){maxlist.get(i);}}return max;}public ListInteger largestValues(TreeNode root){ListInteger listnew ArrayList();QueueTreeNode queuenew LinkedList();if (rootnull){return list;}else {queue.offer(root);}TreeNode node;while (!queue.isEmpty()){ListInteger lst new ArrayList();int size queue.size();for (int i 0; i size; i) {nodequeue.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){QueueNode queuenew LinkedList();if (rootnull){return null;}else {queue.offer(root);}Node node;while (!queue.isEmpty()){int size queue.size();for (int i 0; i size; i) {nodequeue.poll();if (isize-1){node.nextnull;}else {node.nextqueue.peek();}if (node.left!null){queue.offer(node.left);}if (node.right!null){queue.offer(node.right);}}}return root;}
