二叉树的最大宽度

import java.util.*;

public class Solution {
    class IndexTreeNode {
        public Integer val;
        public Integer index;
        public IndexTreeNode left;
        public IndexTreeNode right;

        public IndexTreeNode (TreeNode node, Integer index) {
            this.val = node.val;
            this.index = index;
            this.left = node.left == null ? null : new IndexTreeNode(node.left, 2 * index + 1);
            this.right = node.right == null ? null : new IndexTreeNode(node.right, 2 * index + 2);
        }
    }
    
    public int widthOfBinaryTree (TreeNode root) {
        if (root == null) {
            return 0;
        }
        int ans = 1;
        Queue<IndexTreeNode> queue = new LinkedList<>();
        queue.offer(new IndexTreeNode(root, 0));
        while (!queue.isEmpty()) {
            IndexTreeNode head = null;
            IndexTreeNode tail = null;
            for (int s = queue.size(); s > 0; --s) {
                IndexTreeNode n = queue.poll();
                IndexTreeNode[] children = new IndexTreeNode[]{ n.left, n.right };
                for (IndexTreeNode child : children) {
                    if (child != null) {
                        queue.offer(child);
                        if (head == null) {
                            head = child;
                        }
                        tail = child;
                    }
                }
            }
            if (head != null && tail != null) {
                ans = tail.index - head.index + 1;
            }
        }
        return ans;
    }

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int widthOfBinaryTree (TreeNode root) {
        // write code here
        if(root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int maxWidth = 0;
        while(!queue.isEmpty()){
            TreeNode cur = null;
            int size = queue.size();
            ArrayList<TreeNode> array = new ArrayList<>();
            for(int i = 0; i < size; i++){
                cur = queue.poll();
                array.add(cur);//将每一层的所有节点收集，包括空
                if(cur != null){
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }
                    
            }
            int start = 0, end = 0, width = 0;
            //找第一个不为空的
            for(int i = 0; i < array.size(); i++){
                if(array.get(i) != null) {
                    start = i;
                    break;
                }
            }
            //找最后一个不为空的
            for(int i = array.size()-1; i >= 0; i--){
                if(array.get(i) != null) {
                    end = i;
                    break;
                }
            }
            //计算宽度
            //如果某一层全空，也会计算宽度为1，但不影响最终结果正确
            width = end - start + 1;
            //更新宽度
            if(width > maxWidth)
                maxWidth = width;
        }
        return maxWidth;
    }
}最后一个样例过不了，但是我怎么觉得答案有点问题。。。

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int widthOfBinaryTree (TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 遍历的当前节点
        TreeNode currentNode = node;
        // 下一层开始节点
        TreeNode nextStart = null;
        // 下一层结束节点
        TreeNode nextEnd = node;
        // 当前层结束节点
        TreeNode currentEnd = node;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        int count = 0;
        int maxCount = 0;
        while (!queue.isEmpty()) {
            currentNode = queue.poll();
            if (currentNode == null) {
                count++;
                continue;
            }
            if (currentNode.left != null) {
                nextEnd = currentNode.left;
                nextStart = nextStart != null ? nextStart : currentNode.left;
                queue.add(currentNode.left);
            } else {
                if (currentNode.left == null && nextStart != null) {
                    queue.add(currentNode.left);
                }
            }

            if (currentNode.right != null) {
                nextEnd = currentNode.right;
                nextStart = nextStart != null ? nextStart : currentNode.right;
                queue.add(currentNode.right);
            } else {
                if (currentNode.right == null && nextStart != null) {
                    queue.add(currentNode.left);
                }
            }
            count++;
            if (currentEnd == currentNode) {
                nextStart = null;
                currentEnd = nextEnd;
                maxCount = Math.max(count, maxCount);
                count = 0;
            }
        }
        return maxCount;
    }
}