获取二叉树的最大宽度

题：

给定二叉树的根节点，获取该树的最大宽度

例：

考虑下图

级别1的宽度为1。因为它只有1个节点。
级别2的宽度为2。因为它只有2个节点。
级别3的宽度为4。因为它只有4个节点。

解：

在进行级别顺序遍历时，计算每个级别上的节点数。

然后获取每个级别的最大节点数并显示结果。

解

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};

int get_max_width(Node *root) 
{ 
    if (root == NULL) 
        return 0; 
  
    int result = 0; 
  
    queue<Node*> q; 
    q.push(root); 
    while (!q.empty()) 
    { 
        //get the size of the queue
        int count = q.size() ; 

        result = max(count, result); 
  
        //this loop will get all the nodes at a particular level
        while (count > 0) 
        { 
            Node *temp = q.front(); 
            q.pop(); 
  
            if (temp->left != NULL) 
                q.push(temp->left); 
            if (temp->right != NULL) 
                q.push(temp->right); 

            count --;
        } 
    } 
  
    return result; 
} 

int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    cout<<"The max width of the binary tree is = "<< get_max_width(root)<<endl;

    return 0;  
}  

输出：

The max width of the binary tree is = 4