Leetcode--Java--662. 二叉树最大宽度

题目描述

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

样例描述

思路

二叉树堆式存储 + 层序遍历

1. 显然每个结点的值并没用处，可以用来存储堆式存储位置编号，则每层的宽度就是最小的编号和最大的宽度之差加一，在层序遍历中更新维护最大宽度即可
2. 这里用LinkList子类，不用Deque/Queue因为getLast和getFirst是子类独有的方法，父类无法调用。如果不记得这两个方法，直接在遍历中记录最小和最大编号，也就是遍历每一层时的第一个和最后一个 （没必要比较值的大小因为可能越界，只要是位置上的第一个和最后一个即可）

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
          
   
    public int widthOfBinaryTree(TreeNode root) {
          
   
        if (root == null) {
          
   
            return 0;
        }
        LinkedList<TreeNode> q = new LinkedList<>();
        root.val = 1;
        q.offer(root);
        int res = 0;
        while (!q.isEmpty()) {
          
   
            //当前层的宽度，最小编号和最大编号之差
            // int width = q.getLast().val - q.getFirst().val + 1;
            int minp = Integer.MAX_VALUE, maxp = Integer.MIN_VALUE;
            int size = q.size();
            for (int i = 0; i < size; i ++ ) {
          
   
                TreeNode node = q.poll();
                //记录本层的最小编号和最大编号
                if (i == 0) minp = node.val;
                if (i == size - 1) maxp = node.val;
                 if (node.left != null) {
          
   
                    node.left.val = 2 * node.val;
                    q.offer(node.left);
                }
                if (node.right != null) {
          
   
                    node.right.val = 2 * node.val + 1;
                    q.offer(node.right);
                }
            }
            // res = Math.max(res, width);
            res = Math.max(res, maxp - minp + 1);
        }
        return res;
    }
}