1.最宽行是多宽?广度优先遍历

使用二叉树的广度优先搜索(BFS),通过nextEndcurEnd来分割不同的层数,nextEnd是由判断子节点是否存在更新,curEnd在层与层之间切换时更新为nextENd

#include <iostream>
#include <queue>

struct Node
{
    int val;
    Node * left;
    Node * right;
    Node(int v) :val(v), left(nullptr), right(nullptr) {};
};


int maxWidthLevel(Node * node)
{
    int maxWidLev = 0;
    int maxWidth = 0;
    int cur_level = 0;
    int cur_width = 0;
    Node * nowNode = nullptr;
    std::queue<Node *> nodeQueue ;
    nodeQueue.emplace(node);
    Node * curEnd = node;
    Node * nextEnd = nullptr;
    while (1)
    {
        if (nodeQueue.empty())
        {
            break;
        }
        nowNode = nodeQueue.front();
        nodeQueue.pop();
        if (nowNode != nullptr)
        {
            cur_width++;
            if (nowNode->left != nullptr)
            {
                nodeQueue.emplace(nowNode->left);
                nextEnd = nowNode->left;
            }
            if (nowNode->right != nullptr)
            {
                nodeQueue.emplace(nowNode->right);
                nextEnd = nowNode->right;
            }
        }
        
        if (nowNode == curEnd)//一行截止了
        {
            if (cur_width > maxWidth)
            {
                maxWidth = cur_width;
                maxWidLev = cur_level;//更新最大宽度
            }
            curEnd = nextEnd;//更新下一行的截止node
            cur_width = 0;
            cur_level++;
        }
    }
    return maxWidLev;
}

int main()
{
    Node * begin = new Node(1);
    Node * nowpos = begin;
    nowpos->left = new Node(2);
    nowpos->left->left = new Node(3);
    nowpos->left->right = new Node(3);
    begin->right = new Node(4);
    //begin->right->left = new Node(5);
    int maxlev =  maxWidthLevel(begin);
    std::cout << maxlev;
    return 0;
}

2. 二叉树的深度是多少?

使用二叉树的广度优先搜索(BFS),统计每层数,通过nextEndcurEnd来分割不同的层数。

#include <iostream>
#include <queue>

struct Node
{
    int val;
    Node * left;
    Node * right;
    Node(int v) :val(v), left(nullptr), right(nullptr) {};
};

int countMaxDepth(Node * node)
{
    if (node == nullptr)
        return 0;
    std::queue<Node *> node_Queue;
    Node * nowNode = node;
    node_Queue.emplace(nowNode);
    int maxDepth = 0;
    Node * NextEnd = nullptr;
    Node * curEnd = node;
    while (1)
    {
        if (node_Queue.empty())
        {
            break;
        }
        nowNode = node_Queue.front();
        node_Queue.pop();
        if (nowNode->left != nullptr)
        {
            node_Queue.emplace(nowNode->left);
            NextEnd = nowNode->left;
        }
        if (nowNode->right != nullptr)
        {
            node_Queue.emplace(nowNode->right);
            NextEnd = nowNode->right;
        }
        if (nowNode == curEnd)
        {
            curEnd = NextEnd;
            maxDepth++;
        }
    }
    return maxDepth;
}

int main()
{
    Node * begin = new Node(1);
    Node * nowpos = begin;
    nowpos->left = new Node(2);
    nowpos->left->left = new Node(3);
    nowpos->left->right = new Node(3);
    begin->right = new Node(4);
    begin->right->left = new Node(5);
    std:: cout << countMaxDepth(begin);
    return 0;
}

3. 是否是完全二叉树

不是完全二叉树有两个条件,第一是每个节点的左侧无子节点,而右侧有子节点,此时二叉树一定不是完全二叉树。

#include <iostream>
#include <queue>

struct Node
{
    int val;
    Node * left;
    Node * right;
    Node(int v) :val(v), left(nullptr), right(nullptr) {};
};

bool isCBT(Node * node)
{
    if (node == nullptr)//如果节点为空,则为满二叉树
        return true;
    Node * nowNode = node;
    //Node * curEnd = node;
    //Node * nextEnd = nullptr;
    std::queue<Node *> NodeQueue;
    NodeQueue.emplace(nowNode);
    bool flag = false;
    //有右节点,无左节点。则返回false
    //曾经有前面的节点是空节点。
    while (1)
    {
        
        if ((flag == true && (nowNode->left != nullptr || nowNode->right != nullptr)) ||
            nowNode->left == nullptr && nowNode->right != nullptr)
        {
            return false;
        }
        if (nowNode->left == nullptr)
        {
            NodeQueue.emplace(nowNode->left);
            //nextEnd = nowNode->left;
        }
        else flag = true;
        if (nowNode->right == nullptr)
        {
            NodeQueue.emplace(nowNode->right);
            //nextEnd = nowNode->right;
        }
        else flag = true;
        
        if (NodeQueue.empty())
        {
            break;
        }
        /*if (nowNode == curEnd)
        {
            curEnd = nextEnd;
        }*/
    }
    return true;
}

int main()
{
    Node * begin = new Node(1);
    Node * nowpos = begin;
    nowpos->left = new Node(2);
    nowpos->left->left = new Node(3);
    nowpos->left->right = new Node(3);
    begin->right = new Node(4);
    begin->right->left = new Node(5);
    std::cout << isCBT(begin);
    system("pause");
    return 0;
}