题目描述

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

题目链接

https://leetcode.com/problems/maximum-width-of-binary-tree/

方法思路

The idea is to traverse all the node in the tree in level order(Here I use one Queue to store each level’s nodes. The time I traverse each level is the queue’s size(the number of nodes from upper level)). Each time a node is traversed, the position of the node(as it is in a full binary tree) is stored in the HashMap. If the position of the parent node is ‘n’, then the left child is ‘2 * n’ and the right child is ‘2 * n + 1’. The width of each level is the last node’s position in this level subtracts the first node’s position in this level plus 1.

class Solution {
    //Runtime: 2 ms, faster than 93.37%
    //Memory Usage: 38.7 MB, less than 13.14%
    public int widthOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        Map<TreeNode, Integer> m = new HashMap<>();
        q.offer(root);
        m.put(root, 1);
        int curW = 0;
        int maxW = 0;
        while(!q.isEmpty()){
            int size = q.size();
            int start = 0;
            int end = 0;
            for(int i = 0; i < size; i++){
                TreeNode node = q.poll();
                if(i == 0) start = m.get(node);
                if(i == size - 1) end = m.get(node);
                if(node.left != null){
                    m.put(node.left, m.get(node) * 2);
                    q.offer(node.left);
                }
                if(node.right != null){
                    m.put(node.right, m.get(node) * 2 + 1);
                    q.offer(node.right);
                }
            }
            curW = end - start + 1;
            maxW = Math.max(curW, maxW);
        }
        return maxW;
    }
}