526互联

力扣 662 https://leetcode.cn/problems/maximum-width-of-binary-tree/

发布时间 2023-05-27 22:15:21作者: 故里oc

需要了解树的顺序存储

如果是普通的二叉树 ，底层是用链表去连接的

如果是满二叉树，底层用的是数组去放的，而数组放的时候 会有索引对应 当前父节点是索引i，下一个左右节点就是2i,2i+1

利用满二叉树的索引特征

所以需要对每个节点进行一个索引赋值，赋值在队列中，队列用数组表示

核心代码如下

public int widthOfBinaryTreeBetter(TreeNode root) {
    Queue<Pair<TreeNode,Integer>> queue = new LinkedList<>();


    queue.add(new Pair<>(root,1));
    int res=0;
    while (!queue.isEmpty()){

        int size = queue.size();
        int left=-1;
        int right=-1;
        for (int i = 0; i < size; i++) {
            Pair<TreeNode, Integer> poll = queue.poll();
            Integer value = poll.getValue();
            if (left==-1){
                left=value;
            }
            right=value;

            TreeNode temp = poll.getKey();
            if (temp.left!=null){
                queue.add(new Pair<>(temp.left,value*2));
            }
            if (temp.right!=null){
                queue.add(new Pair<>(temp.right,value*2+1));
            }
            res=Math.max(right-left+1,res);
        }

    }
    return res;
}