本文共 8409 字，大约阅读时间需要 28 分钟。

原文地址：

已知一个二叉树，写一个函数得到已知二叉树的最大宽度。一个树的宽度指的是所有层的宽度的最大值。

我们想一下下面的例子：

1        /  \       2    3     /  \     \    4    5     8               /  \             6    7

对于上面这个树：

第一层的宽度是1，

所以树的宽度是3。

方法1（用层级遍历）

这个方法主要有两个函数。一个是计数一个已知层的节点的数目（getWidth），另一个是得到树的最大宽度（getMaxWidth）。getMaxWidth()利用getWidth()得到从根开始的所有层的宽度。

/*Function to print level order traversal of tree*/getMaxWidth(tree)maxWdth = 0for i = 1 to height(tree)  width =   getWidth(tree, i);  if(width > maxWdth)       maxWdth  = widthreturn width

/*Function to get width of a given level */getWidth(tree, level)if tree is NULL then return 0;if level is 1, then return 1;  else if level greater than 1, then    return getWidth(tree->left, level-1) +     getWidth(tree->right, level-1);

// Java program to calculate width of binary tree/* A binary tree node has data, pointer to left child   and a pointer to right child */class Node {    int data;    Node left, right;    Node(int item)     {        data = item;        left = right = null;    }}class BinaryTree {    Node root;    /* Function to get the maximum width of a binary tree*/    int getMaxWidth(Node node)     {        int maxWidth = 0;        int width;        int h = height(node);        int i;        /* Get width of each level and compare            the width with maximum width so far */        for (i = 1; i <= h; i++)         {            width = getWidth(node, i);            if (width > maxWidth)                maxWidth = width;        }        return maxWidth;    }    /* Get width of a given level */    int getWidth(Node node, int level)     {        if (node == null)            return 0;        if (level == 1)            return 1;        else if (level > 1)            return getWidth(node.left, level - 1)                    + getWidth(node.right, level - 1);        return 0;    }    /* UTILITY FUNCTIONS */    /* Compute the "height" of a tree -- the number of     nodes along the longest path from the root node     down to the farthest leaf node.*/    int height(Node node)     {        if (node == null)            return 0;        else        {            /* compute the height of each subtree */            int lHeight = height(node.left);            int rHeight = height(node.right);            /* use the larger one */            return (lHeight > rHeight) ? (lHeight + 1) : (rHeight + 1);        }    }    /* Driver program to test above functions */    public static void main(String args[])     {        BinaryTree tree = new BinaryTree();        /*        Constructed bunary tree is:              1            /  \           2    3         /  \    \        4   5     8                  /  \                6   7         */        tree.root = new Node(1);        tree.root.left = new Node(2);        tree.root.right = new Node(3);        tree.root.left.left = new Node(4);        tree.root.left.right = new Node(5);        tree.root.right.right = new Node(8);        tree.root.right.right.left = new Node(6);        tree.root.right.right.right = new Node(7);        System.out.println("Maximum width is " + tree.getMaxWidth(tree.root));    }}// This code has been contributed by Mayank Jaiswal

时间复杂度：最差情况下是$O(n^2)$。

我们可以用队列基于层级遍历来优化这个方法的时间复杂度。基于层级顺序的队列在最坏的情况下花费O(n)。

方法2（用队列做层级遍历）

在这个方法中，我们在队列中保存了当前层的所有孩子节点，然后在指定层的层级遍历完成之后计算这一层节点的个数。因为队列现在保存了下一层的所有节点，所以我们用队列的大小很容易地得到下一层节点的总数。然后我们根据相同的过程处理下一层。我们存储并更新每一层找到的节点最大数目。

// A queue based C++ program to find maximum width// of a Binary Tree#include
   
    using namespace std ;/* A binary tree node has data, pointer to left child   and a pointer to right child */struct Node{    int data ;    struct Node * left ;    struct Node * right ;};// Function to find the maximum width of the tree// using level order traversalint maxWidth(struct Node * root){    // Base case    if (root == NULL)        return 0;    // Initialize result    int result = 0;    // Do Level order traversal keeping track of number    // of nodes at every level.    queue
    
      q;    q.push(root);    while (!q.empty())    {        // Get the size of queue when the level order        // traversal for one level finishes        int count = q.size() ;        // Update the maximum node count value        result = max(count, result);        // Iterate for all the nodes in the queue currently        while (count--)        {            // Dequeue an node from queue            Node *temp = q.front();            q.pop();            // Enqueue left and right children of            // dequeued node            if (temp->left != NULL)                q.push(temp->left);            if (temp->right != NULL)                q.push(temp->right);        }    }    return result;}/* Helper function that allocates a new node with the   given data and NULL left and right pointers. */struct Node * newNode(int data){    struct Node * node = new Node;    node->data = data;    node->left = node->right = NULL;    return (node);}int main(){    struct Node *root = newNode(1);    root->left        = newNode(2);    root->right       = newNode(3);    root->left->left  = newNode(4);    root->left->right = newNode(5);    root->right->right = newNode(8);    root->right->right->left  = newNode(6);    root->right->right->right  = newNode(7);    /*   Constructed Binary tree is:                 1               /   \             2      3           /  \      \          4    5      8                    /   \                   6     7    */    cout << "Maximum width is "         << maxWidth(root) << endl;    return 0;}// This code is contributed by Nikhil Kumar Singh(nickzuck_007)
    
   

方法3（用先序遍历）

在这个方法中，我们建立一个临时数组count[]，大小等于树的高度。我们初始化count中所有的值为0，用先序遍历遍历这个树，并填充count，这样二叉树的每一层的节点数目就包含在了count数组中。

// Java program to calculate width of binary tree/* A binary tree node has data, pointer to left child   and a pointer to right child */class Node {
       int data;    Node left, right;    Node(int item)     {        data = item;        left = right = null;    }}class BinaryTree {
       Node root;    /* Function to get the maximum width of a binary tree*/    int getMaxWidth(Node node)     {        int width;        int h = height(node);        // Create an array that will store count of nodes at each level        int count[] = new int[10];        int level = 0;        // Fill the count array using preorder traversal        getMaxWidthRecur(node, count, level);        // Return the maximum value from count array        return getMax(count, h);    }    // A function that fills count array with count of nodes at every    // level of given binary tree    void getMaxWidthRecur(Node node, int count[], int level)     {        if (node != null)         {            count[level]++;            getMaxWidthRecur(node.left, count, level + 1);            getMaxWidthRecur(node.right, count, level + 1);        }    }    /* UTILITY FUNCTIONS */    /* Compute the "height" of a tree -- the number of     nodes along the longest path from the root node     down to the farthest leaf node.*/    int height(Node node)     {        if (node == null)             return 0;        else        {            /* compute the height of each subtree */            int lHeight = height(node.left);            int rHeight = height(node.right);            /* use the larger one */            return (lHeight > rHeight) ? (lHeight + 1) : (rHeight + 1);        }    }    // Return the maximum value from count array    int getMax(int arr[], int n)     {        int max = arr[0];        int i;        for (i = 0; i < n; i++)         {            if (arr[i] > max)                max = arr[i];        }        return max;    }    /* Driver program to test above functions */    public static void main(String args[])     {        BinaryTree tree = new BinaryTree();        /*        Constructed bunary tree is:              1            /  \           2    3          / \    \         4   5    8                 / \                6   7 */        tree.root = new Node(1);        tree.root.left = new Node(2);        tree.root.right = new Node(3);        tree.root.left.left = new Node(4);        tree.root.left.right = new Node(5);        tree.root.right.right = new Node(8);        tree.root.right.right.left = new Node(6);        tree.root.right.right.right = new Node(7);        System.out.println("Maximum width is " +                            tree.getMaxWidth(tree.root));    }}// This code has been contributed by Mayank Jaiswal

时间复杂度：$O(n)$

转载地址：http://gkhii.baihongyu.com/