求二叉树最宽的层有多少个节点

一、思路:

在按层遍历的基础上进行改写

(1)准备currentLevelEnd(表示当前层的结束节点)、nextLevelEnd(表示下一层的结束节点)、currentWeight(表示当前层的宽度)、maxWeight(表示最大宽度)四个变量。

(2)currentLevelEnd修改为二叉树的头节点(其他均为默认值),头节点入队列。

(3)从队列中弹出一个节点,每出队一个节点则currentWeight加一,出队节点有左孩子则左孩子入队,有右孩子则右孩子入队,有节点入队则将nextLevelEnd修改为当前入队的节点(为下一层查找做准备)。

(4)判断第3步出队的节点是否等于currentLevelEnd。

是,则修改maxWeight为当前最大宽度,currentWeight重置,currentLevelEnd修改为nextLevelEnd,nextLevelEnd重置;

否,则继续执行第3步。

(5)一直执行第3、4步,直到队列为空。

/**
 * @author Java和算法学习:周一
 */
public static int treeMaxWidth(Node head) {
    if (head == null) {
        return 0;
    }

    Queue queue = new LinkedList<>();
    Node currentLevelEnd = head;
    Node nextLevelEnd = null;
    int currentWidth = 0;
    int maxWidth = 0;

    queue.offer(head);
    while (!queue.isEmpty()) {
        Node current = queue.poll();
        // 每次从队列中弹出节点时,当前层的宽度都加一
        currentWidth++;

        // 有孩子节点入队时就修改下一层的结束节点
        if (current.left != null) {
            queue.offer(current.left);
            nextLevelEnd = current.left;
        }
        if (current.right != null) {
            queue.offer(current.right);
            nextLevelEnd = current.right;
        }

        // 如果当前出队的节点是当前层的结束节点
        if (current == currentLevelEnd) {
            // 修改最大宽度
            maxWidth = Math.max(maxWidth, currentWidth);
            // 当前层宽度重置
            currentWidth = 0;
            // 当前层的结束节点修改,表明下一次循环时开始统计下一层的宽度
            currentLevelEnd = nextLevelEnd;
            // 下一层结束节点重置
            nextLevelEnd = null;
        }
    }

    return maxWidth;
}

二、对数器源码

/**
 * 对数器方法
 *     
 * @author Java和算法学习:周一
 */
public static int treeMaxWidth1(Node head) {
    if (head == null) {
        return 0;
    }
    Queue queue = new LinkedList<>();
    queue.add(head);
    // key:节点,value:节点在哪一层
    HashMap levelMap = new HashMap<>(16);
    levelMap.put(head, 1);
    // 当前来到哪一层
    int curLevel = 1;
    // 当前层的宽度
    int curLevelWidth = 0;
    // 最大宽度
    int max = 0;
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        int curNodeLevel = levelMap.get(cur);
        if (cur.left != null) {
            levelMap.put(cur.left, curNodeLevel + 1);
            queue.add(cur.left);
        }
        if (cur.right != null) {
            levelMap.put(cur.right, curNodeLevel + 1);
            queue.add(cur.right);
        }
        // 当前节点还是在当前层
        if (curNodeLevel == curLevel) {
            curLevelWidth++;
        } else {
            // 当前层已经遍历完毕
            max = Math.max(max, curLevelWidth);
            // 来到下一层
            curLevel++;
            // 当前节点已经是下一层的了,也就是下一层已经有一个节点了,宽度自然是1
            curLevelWidth = 1;
        }
    }
    // 最后一层的宽度没有和max比较,所以这里要再比较一次
    max = Math.max(max, curLevelWidth);
    return max;
}

本文全部代码:https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/TreeMaxWidth.java

你可能感兴趣的