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));

    }

}