之前我们已经实现了二叉树的层序遍历算法8:LeetCode_二叉树的层序遍历_chen_yao_kerr的博客-CSDN博客
和二叉树的序列化与反序列化算法19:LeetCode_二叉树序列化与反序列化(层序)_chen_yao_kerr的博客-CSDN博客他们都是用到了二叉树的层序遍历相关知识,下面再来看一个关于二叉树层序遍历的算法题:
题目:二叉树通常有很多层,每一层的节点数量有可能都是不同的,设计一种算法,找到二叉树的最宽的层一共有多少节点
package code03.二叉树_02; import java.util.LinkedList; import java.util.Queue; /** * 求二叉树最宽的层有多少个节点 */ public class Code02_TreeMaxWidth { static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } // /** * 二叉树层序遍历 * 基本思路就是每一层遍历完以后,统计当前层数的节点数, * 然后根之前的节点最大值做比较,一直更新宽度最大值 * 最终返回的就是二叉树最大层中节点的个数 */ public int maxWidth(TreeNode root) { //边界值判断 if (root == null) { return 0; } //逐层搜集,首先收集根节点,并存入队列。印证思路第1步 Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int max = 0; //当前已经统计完最宽层的节点数 int curLevelNodes = 0; //当前层的节点数 TreeNode curEnd = root; //本层结束节点 TreeNode nextEnd = null; //下一层结束节点 TreeNode cur = null; while (!queue.isEmpty()) { cur = queue.poll(); if (cur.left != null) { queue.add(cur.left); nextEnd = cur.left; } if (cur.right != null) { queue.add(cur.right); nextEnd = cur.right; } curLevelNodes++; //当前层最后一个节点,代表当前层已经全部遍历结束 if (cur == curEnd) { //当前层的结束节点切换到下一层结束节点处,为下一层节点遍历做准备 curEnd = nextEnd; //之前层节点数的最大值 和 当前层节点数比较,得到最新的最宽层的节点数 max = Math.max(curLevelNodes, max); //重置当前层的节点数,为下一层做准备 curLevelNodes = 0; } } return max; } public static void main(String[] args) { TreeNode tree = new TreeNode(1); tree.left = new TreeNode(2); tree.right = new TreeNode(3); tree.left.left = new TreeNode(4); tree.left.right = new TreeNode(5); tree.right.left = new TreeNode(6); tree.right.right = new TreeNode(7); //最大层的宽度为 4 tree.left.left.left = new TreeNode(8); Code02_TreeMaxWidth test = new Code02_TreeMaxWidth(); int with = test.maxWidth(tree); System.out.println("最大宽度为 :" + with); } }
标签:遍历,TreeNode,层序,二叉树,new,20,节点,left
From: https://www.cnblogs.com/chen1-kerr/p/17143630.html