随笔记录

算法-二叉树-宽度优先遍历&树宽度

2022-4-10 diaba 笔试题

package com.jiucaiyuan.net.algrithm.tree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树的宽度优先遍历（求一个二叉树的宽度）
 * 使用辅助工具队列LinkedList，压入队列，出队时进行访问
 *
 * @Author jiucaiyuan  2022/4/9 23:15
 * @mail services@jiucaiyuan.net
 */

public class TreeMaxWidth {
    /**
     * 宽度优先遍历
     *
     * @param root
     */
    public static void width(Node root) {
        if (root == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            System.out.print(curr.value + " ");
            if (curr.left != null) {
                queue.add(curr.left);
            }
            if (curr.right != null) {
                queue.add(curr.right);
            }
        }
    }

    /**
     * 宽度优先遍历，得到树的最大宽度
     *
     * @param root
     */
    public static int getTreeWidth(Node root) {
        if (root == null) {
            return 0;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        HashMap<Node, Integer> levelMap = new HashMap<>();
        levelMap.put(root, 1);
        int currLevel = 1;
        int currLevelNodes = 0;
        int maxWidth = Integer.MIN_VALUE;
        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            if (levelMap.get(curr) == currLevel) {
                currLevelNodes++;
            } else {
                maxWidth = Math.max(maxWidth, currLevelNodes);
                currLevel++;
                currLevelNodes = 1;
            }
            if (curr.left != null) {
                levelMap.put(curr.left, levelMap.get(curr) + 1);
                queue.add(curr.left);
            }
            if (curr.right != null) {
                levelMap.put(curr.right, levelMap.get(curr) + 1);
                queue.add(curr.right);
            }
        }
        //因为都是到下一层第一个节点时计算上一层宽度，所以最后要处理最后一层的结算
        maxWidth = Math.max(maxWidth, currLevelNodes);
        return maxWidth;
    }

    public static void main(String[] args) {
        Node root = new Node();
        root.value = 3;

        root.left = new Node();
        root.left.value = 9;

        root.left.left = new Node();
        root.left.left.value = 35;

        root.right = new Node();
        root.right.value = 20;

        root.right.left = new Node();
        root.right.left.value = 15;

        root.right.right = new Node();
        root.right.right.value = 7;
        System.out.print("宽度优先遍历结果：");
        width(root);
        System.out.println("----树的宽度是=" + getTreeWidth(root));

        Node root1 = new Node();
        root1.value = 1;

        root1.left = new Node();
        root1.left.value = 2;

        root1.right = new Node();
        root1.right.value = 2;

        root1.left.left = new Node();
        root1.left.left.value = 3;

        root1.left.right = new Node();
        root1.left.right.value = 3;

        root1.left.left.left = new Node();
        root1.left.left.left.value = 4;

        root1.left.left.right = new Node();
        root1.left.left.right.value = 4;
        System.out.print("宽度优先遍历结果：");
        width(root1);
        System.out.println("----树的宽度是=" + getTreeWidth(root1));
    }
}