662. Maximum width of binary tree

Note: Take the length between non-empty endpoints

Ideas:

• It is not possible to simply order through and count the number of nodes on each layer (queue.size()), because we take the length between non-empty endpoints and null in between counts.
• Each non-empty node is assigned a number, and the empty node counts.
• Then the width of each layer = the difference between the first and last non-empty node labels +1
• Get a queue record number to synchronize with the queue of the record node.

.

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();// Record the node queue
        LinkedList<Integer> indexQ = new LinkedList<>();// Record the index queue
        queue.add(root);
        indexQ.add(0);
        int max = 1;
        while(! queue.isEmpty()) {int size = queue.size();
            int start = indexQ.getFirst();
            int end = indexQ.getLast();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.removeFirst();// Synchronously exit the column
                int index = indexQ.removeFirst();// Synchronously exit the column
                if(node.left ! =null) {
                    queue.add(node.left);// Synchronize the columns
                    indexQ.add(index * 2 + 1);// Synchronize the columns
                }
                if(node.right ! =null) {
                    queue.add(node.right);// Synchronize the columns
                    indexQ.add(index * 2 + 2);// Synchronize the columns}}int idxSize = end - start + 1;// Can't get lastfirst here, get is the next line. If it was the last line, idxQ would be empty by this point
            max = Math.max(idxSize, max);

        }
        returnmax; }}Copy the code