劍指offer之分行從上到下列印二叉樹

1 題目

分行從上到下列印二叉樹

1.                   2
2.                3    5           
3.              1  4  2  3      

我們列印如下

1. 2
2. 
3. 3     5
4. 
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 運作結果

1. 2
2. 3       5
3. 1       4       2       3      

5 總結

通過第一行的列印的個數，我們找到第二列列印的個數，通過第二行列印的個數，我們需要列印第三行需要列印的個數，我們可以用2個變量來搞定。