输出一个二叉树的宽度
思路:二叉树的层序遍历(力扣102)的简单变形,记录下每层的节点个数,取最大值即可。
二叉树的层序遍历--打印
public static void level(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (root != null || !queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.println(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
二叉树的层序遍历--带返回值
public static List<List<Integer>> level2(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); level.add(new Integer(node.val)); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } result.add(level); } return result; }
二叉树的层序遍历--最大宽度
public static Integer getWidth(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); Integer maxSize = 0; while (!queue.isEmpty()) { int size = queue.size(); maxSize = Math.max(maxSize, size); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } } return maxSize; }