题解 | #牛群的最大宽度#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int maxWidthOfCows(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> treeNodeQueue = new LinkedList<>();
        Queue<Integer> indexQueue = new LinkedList<>();
        treeNodeQueue.add(root);
        indexQueue.add(1);
        int maxWidth = 0;
        while (!treeNodeQueue.isEmpty()) {
            int size = treeNodeQueue.size();
            Integer left = indexQueue.peek();
            Integer right = left;
            for (int i = 0; i < size; i++) {
                assert !treeNodeQueue.isEmpty();
                TreeNode treeNode = treeNodeQueue.poll();
                assert !indexQueue.isEmpty();
                int index = indexQueue.poll();
                right = index;

                if (treeNode.left != null) {
                    treeNodeQueue.add(treeNode.left);
                    indexQueue.add(index * 2);
                }
                if (treeNode.right != null) {
                    treeNodeQueue.add(treeNode.right);
                    indexQueue.add(index * 2 + 1);
                }
            }
            maxWidth = Math.max(maxWidth, right - left + 1);
        }
        return maxWidth;
    }
}

本题知识点分析：

1.二叉树层序遍历

2.链表队列

3.数学模拟

4.API函数Math.max

本题解题思路分析：

1.分别创建队列，用于存储节点和结点的索引，比如 第一个根节点索引就是1，它的左节点是1*2=2，右节点是1*2+1=3

2.将根节点和索引分别放入队列

3.当节点的队列不为空时，先计算队列大小，先分别从队列中取出此时的节点和索引，assert断言队列不为空的时候，遍历从0到size，将index赋值给右端点，因为每次的左端点在都遍历队列时确定，如果左右子节点不为空，那么分别放入两个队列，注意左右节点索引的区别，遍历完一次队列后，更新maxWidth的较大值。

4.将maxWidth进行返回

本题使用编程语言: Java

如果你觉得本篇文章对你有帮助的话，可以点个赞支持一下，感谢~