二叉树的最大宽度(BFS)

问题描述

给你一个二叉树，返回它的最大宽度。
二叉树的某一层宽度指的是在那一层，最右边结点和最左边结点之间的结点个数（如果中间存在空结点，也包括在内）

分析

编写这样一个函数，传入一个初始化好的二叉树，返回它最大的宽度。
如何获得它的最大宽度？首先可以考虑通过遍历每一层的结点，然后去计算这些结点的数量，因为要求中间即使有结点不存在，也要视作存在，这可能要对原二叉树的结构做些改动，不太方便。
为了方便，我们可以给这些结点赋以特殊的value, 按照完全二叉树的概念，根节点为1，第一个左子树的根节点为2，第一个右子树的根节点为3，…
这样对于每个结点(value为k), 都可以确定它的左子树根节点为2k, 右子树的根节点为2k+1.
宽度=右端点的value值-左端点的value值+1.

通过声明一个双端队列的数据结构.
将二叉树视为满二叉树,不存在的节点也画上去. 每个二叉树的节点的值是它被遍历的顺序. 根节点被首次遍历, 其次是它的左子节点和右子节点.
如果一个节点的值为n, 那么它的左子节点的值为n2, 它的右子节点为n2+1.

首先将根节点入队列. 然后取出该节点. 这个节点被称为出队节点.
如果出队节点存在左子节点, 那么将左子节点入队列; 如果出队节点存在右子节点, 那么将右子节点入队列.
在队列为空之前, 可以获得一批新的节点入队列, 每个节点的值相当于它作为满二叉树的被遍历节点的顺序.

用maxWidth来统计宽度的最大值. width=right-left+1, maxWidth=Math.max(maxWidth,width);

双端队列Deque

利用java中的双端队列结构, 获得二叉树的结点. 根据此题的特点, 让队列先获得二叉树的根节点, 入队列之前先把根节点的值修改成1. 入队列之后, 获得队列的长度1, 而后开始出队列.
根节点出队列之前, 会判断它是否存在子节点, 如果存在, 先将右子结点压入队列, 再将左子节点压入队列. 这样在根结点出队列之前第二层的结点就提前进入了队列. 然后继续这样操作, 直到队列为空.
每次统计width=right-left+1, 并用maxWidth记录最大的宽度.

如何判断结点是属于同一层的?
这个问题很重要, 因为在队列为空之前, 结点会不断入队, 必然既包含了上一层的结点又包含了这一层的结点, 需要判断哪些结点属于同一层, 这样计算出来的宽度才是正确的. 我们是这么做的, 每次执行出队操作之前, 统计一下队列中剩余的结点个数, 保证每次出队的结点都是同一层的. 可以看一下下面的步骤示意.
假设某一时刻某一层有三个结点, 分别记作k, l, m.
此时记录宽度为k-m+1

让k结点出列, 判断它有没有子节点? 假设有, 且左右结点都有, 那么先入队右节点2k+1, 再入队左节点2k

让l结点出列, 判断它有没有子节点? 假设有, 只有左节点, 那么就入队左节点

最后让m结点出列, 判断它有没有子节点? 假设没有, 不操作.

问题来了, 怎么判断出m就是这一层最后的结点呢? 程序显然是不知道的, 我们知道, 所以我们要标记出来, 让程序在弹出这个结点出队列时, 就停一下, 统计一下此时队列的长度, 然后下一次出队时, 次数不超过这个队列的长度, 也在下一次出队列之前把宽度统计出来, 并覆盖最大宽度.
我们来看一下后面的步骤和完整的流程

代码实现

这里用到了java的双端队列的很多api方法, 包括入队, 获得左端点的值, 获得右端点的值, 出队列等.
传入一个二叉树.

1. 首先都是非空判断.
2. 声明一个双端队列, 初始化变量maxWide(最大宽度)
3. 将二叉树根节点入栈, 将它的值修改成1
4. 下面是主体部分, 是一个循环, 循环终止条件是队列为空.
   4.1 结点出队之前总要获得一下队列的长度, 并统计这个时候的宽度, 更新最大宽度.
   4.2 按照队列的长度依次将队列中的结点出队, 这是一个循环, 循环的次数和出队前队列的长度有关
   4.3 每出队一个结点, 判断它是否有左右子节点, 如果有, 先入右子节点, 再入左子节点, 同时更新一下它们的value值. 如果没有, 不操作.
5. 循环结束后, 返回获得的最大的宽度.

public static int getMaxWideTreeNode(TreeNode root){
        if(root == null){
            return 0;
        }
        
        Deque<TreeNode> queue = new LinkedList<>();
        int maxWide = 0;
        queue.offer(root);
        //将二叉树节点重新赋值,新的值为它作为满二叉树层序遍历的顺序.
        root.setData(1);
        
        while(!queue.isEmpty()){
            //获得当前序列的长度, 以及更新最大宽度
            int levelCount = queue.size();
            int left = queue.peekFirst().getData();
            int right = queue.peekLast().getData();
            maxWide = Math.max(maxWide, right - left + 1);
            //按照当前长度将节点一个一个移出队列,在移出的同时,如果该节点有子节点,将子节点加入到队列中
            for(int i = 0; i < levelCount; i++){
                TreeNode node = queue.poll();
                if(node.getLeft() != null){
                    queue.offer(node.getLeft());
                    node.getLeft().setData(node.getData()*2);
                }
                if(node.getRight() != null){
                    queue.offer(node.getRight());
                    node.getRight().setData(node.getData()*2+1);
                }
            }
        }
        return maxWide;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

测试

示例
代码初始化过程如下

public static void main(String[] args) {
//示例1
        TreeNode root = new TreeNode(1);
        TreeNode lchild1 = new TreeNode(3);
        TreeNode rchild1 = new TreeNode(2);
        TreeNode lchild2 = new TreeNode(5);
        TreeNode rchild2 = new TreeNode(3);
        TreeNode rchild3 = new TreeNode(9);
        root.setLeft(lchild1);
        root.setRight(rchild1);
        lchild1.setLeft(lchild2);
        lchild1.setRight(rchild2);
        rchild1.setRight(rchild3);
        int maxWide = FindMaxWideTreeNode.getMaxWideTreeNode(root);
        System.out.println(maxWide);
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16