剑指offer之分行从上到下打印二叉树

1 题目

分行从上到下打印二叉树

                  2
               3    5
             1  4  2  3 

我们打印如下

2

3     5

1     4     2     3

2 分析

之前这篇博客写了通过队列按层打印剑指offer之按层打印树节点

现在无非就是还要按照条件打印，第一次打印1个，然后第二次打印2个，第三次打印4个，我们可以这样，搞2个变量，第一个变量表示这行还没有打印的个数，另外一个变量是下列需要打印的个数，如果这一行还没有打印的个数是0了，我们就把下列需要打印值个数赋值给它，然后下一列变量的个数变量赋值为0.

3 代码实现

#include <iostream>
#include <queue>

using namespace std;

typedef struct Node
{
    int value;
    struct Node* left;
    struct Node* right;
} Node;

void layer_print(Node *head)
{
    if (head == NULL)
    {
       std::cout << "head is NULL" << std::endl;
       return;
    }
    std::queue<Node *> queue;
    queue.push(head);
    //下一列需要打印节点的个数
    int next_print_count = 0;
    //当前这一列还需要打印节点的个数
    int has_print_count = 1;
    while(queue.size())
    {
        Node *node = queue.front();
        std::cout << node->value << "\t";
        if (node->left)
        {
            queue.push(node->left);
            next_print_count++;
        }
        if (node->right)
        {
            queue.push(node->right);
            next_print_count++;
        }
        queue.pop();
        has_print_count--;
        if (has_print_count == 0)
        {
            has_print_count = next_print_count;
            next_print_count = 0;
            std::cout << std::endl;
        }
    }
}

int main()
{
    /*              2
     *           3    5
     *         1  4  2  3
     *
     */
    Node head1, node1, node2, node3, node4, node5, node6;
    Node head2, node7, node8;
    head1.value = 2;
    node1.value = 3;
    node2.value = 5;
    node3.value = 1;
    node4.value = 4;
    node5.value = 2;
    node6.value = 3;

    head1.left = &node1;
    head1.right = &node2;

    node1.left = &node3;
    node1.right = &node4;

    node2.left = &node5;
    node2.right = &node6;

    node3.left = NULL;
    node3.right = NULL;
    node4.left = NULL;
    node4.right = NULL;
    node5.left = NULL;
    node5.right = NULL;
    node6.left = NULL;
    node6.right = NULL;

    layer_print(&head1);
    return 0;
}

4 运行结果

2
3       5
1       4       2       3

5 总结

通过第一行的打印的个数，我们找到第二列打印的个数，通过第二行打印的个数，我们需要打印第三行需要打印的个数，我们可以用2个变量来搞定。