算法面试题-二叉树的宽度

本文主要是介绍算法面试题-二叉树的宽度，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：

求一棵二叉树的宽度

分析：

 先了解二叉树的宽度优先遍历，使用的数据结构是队列:
    1.将root节点放入队列
    2.将队首节点的左/右节点分别入队列，并将对首节点打印并弹出队列
    3.重复步骤2直至队列为空
 所以求树的宽度即在宽度优先遍历的基础上记录每一层的节点个数，需要使用hash表记录每个节点所在的层数:
    1.将root节点放入队列，并用hash表记录该节点的层数为1
    2.将队首节点的左/右节点分别入队列，同时将队首节点出队，并记录左/右节点层数(在队首节点层数的基础上加1就为左/右节点层数)
    3.判断队首节点对应的层数和当前层的大小：如果大于则说明进入了下一层，此时重置当前层的宽度为0；如果等于则将当前层的宽度累加。
    4.将记录的最大宽度和当前层的宽度进行比较

代码实现：

public class TreeMaxWidth {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    // 宽度优先遍历
    public static void breadthFirstTraversal(Node head) {
        if (head == null) {
            return;
        }

        Queue<Node> queue = new LinkedList<>();  // 队列使用的LinkedList实现
        queue.add(head);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            System.out.println(cur.value);
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
    }

    public static int getMaxWidth(Node head) {
        if (head == null) {
            return 0;
        }

        int maxWidth = 0;
        int curWidth = 0;
        int curLevel = 1;

        // 用于记录每个节点对应的层数
        HashMap<Node, Integer> levelMap = new HashMap<>();
        levelMap.put(head, 1);

        Queue<Node> queue = new LinkedList<>();  // 队列使用的LinkedList实现
        queue.add(head);

        Node node = null;
        Node left = null;
        Node right = null;
        while (!queue.isEmpty()) {
            node = queue.poll();
            left = node.left;
            right = node.right;
            // 左/右节点在父节点基础层数上加1
            if (left != null) {
                levelMap.put(left, levelMap.get(node) + 1);
                queue.add(left);
            }
            if (right != null) {
                levelMap.put(right, levelMap.get(node) + 1);
                queue.add(right);
            }

            // 遍历到下一层
            if (levelMap.get(node) > curLevel) {
                curWidth = 0;
                curLevel = levelMap.get(node);
             // 还在同一层进行遍历
            } else {
                curWidth++;
            }
            maxWidth = Math.max(maxWidth, curWidth);

        }
        return maxWidth;

    }

}

这篇关于算法面试题-二叉树的宽度的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！