Daily LeetCode – day0029 0662. Maximum Width of Binary Tree

// 0662. Maximum Width of Binary Tree
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        Queue<Pair> queue = new LinkedList<>();
        queue.offer(new Pair(root, 0L));
        long maxWidth = 1L;
        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            long left = 0L;
            long right = 0L;
            for (int i = 0; i < queueSize; ++i) {
                Pair pair = queue.poll();
                TreeNode node = pair.node;
                long index = pair.index;
                if (i == 0) left = index;
                right = index;
                if (node.left != null) {
                    queue.offer(new Pair(node.left, (index << 1) + 1));
                }
                if (node.right != null) {
                    queue.offer(new Pair(node.right, (index << 1) + 2));
                }
            }
            if (right - left + 1 > maxWidth) {
                maxWidth = right - left + 1;
            }
        }
        return (int) maxWidth;
    }
}

class Pair {
    TreeNode node;
    long index;

    public Pair(TreeNode node, Long index) {
        this.node = node;
        this.index = index;
    }
}
学习笔记:
这是一道二叉树的题目,我使用了宽度优先搜索。
一开始的写法我用了宽度优先搜索,把null的结点也都全部塞进去一起遍历了,这样做的后果就是超时了……
然后我就尝试把结点的下标也都放进去一起,这样就不需要空节点了,但是怎么捆绑呢,想到了用C++的Pair,但是java的Pair是在外置的模块里面,放进去一跑编译都通不过。
实在无奈,就手写了一个Pair类,1ms跑完,超过99.9%还是比较满意的。
这里用了一个日常小技巧,乘以2写成左移1位。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。