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

1 問題

分行從上到下之字行打印二叉樹

比如二叉樹

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

 分行從上到下之字行打印二叉樹結(jié)果如下

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


2 分析

這里我們可以用2個(gè)棧（先進(jìn)后出），先把stack1push根節(jié)點(diǎn)，然后把stack全部彈出來，分別push根節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)到stack2，然后stack2彈出棧里面的每個(gè)節(jié)點(diǎn)，我們分別把每個(gè)節(jié)點(diǎn)的右節(jié)點(diǎn)和左節(jié)點(diǎn)push到stack1,里面去，直到stack1和stack2都是空元素結(jié)束循環(huán)。

 
3 代碼實(shí)現(xiàn)

    #include <iostream>
    #include <stack>
     
    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::stack<Node *> stack1, stack2;
        stack1.push(head);
        while((stack1.size() != 0) || (stack2.size() != 0))
        {
                while (stack1.size() != 0)
            {
                Node *node = stack1.top();
                std::cout << node->value << "\t";
                if (node->left)
                    stack2.push(node->left);
                if (node->right)
                    stack2.push(node->right);
                stack1.pop();
            }
            std::cout << std::endl;
                    while (stack2.size() != 0)
            {
                Node *node = stack2.top();
                std::cout << node->value << "\t";
                if (node->right)
                    stack1.push(node->right);
                if (node->left)
                    stack1.push(node->left);
                stack2.pop();
            }         
                    std::cout << std::endl;
        }
    }
       
     
    int main()
    {
        /*                  2
         *            3            5           
         *         1     4      2      3       
         *      3    2 1   5  1   4  2   3   
         */
        Node head1, node1, node2, node3, node4, node5, node6;
        Node node7, node8, node9, node10, node11, node12, node13, node14;
        head1.value = 2;
        node1.value = 3;
        node2.value = 5;
        node3.value = 1;
        node4.value = 4;
        node5.value = 2;
        node6.value = 3;
        node7.value = 3;
        node8.value = 2;
        node9.value = 1;
        node10.value = 5;
        node11.value = 1;
        node12.value = 4;
        node13.value = 2;
        node14.value = 3;
     
        head1.left = &node1;
        head1.right = &node2;
     
        node1.left = &node3;
        node1.right = &node4;
     
        node2.left = &node5;
        node2.right = &node6;
     
        node3.left = &node7;
        node3.right = &node8;
        node4.left = &node9;
        node4.right = &node10;
        node5.left = &node11;
        node5.right = &node12;
        node6.left = &node13;
        node6.right = &node14;
       
        node7.left = NULL;
        node7.right = NULL;
        node8.left = NULL;
        node8.right =  NULL;
        node9.left = NULL;
        node9.right = NULL;
        node10.left = NULL;
        node10.right = NULL;
        node11.left = NULL;
        node11.right = NULL;
        node12.left = NULL;
        node12.right = NULL;
        node13.left = NULL;
        node13.right = NULL;
        node14.left = NULL;
        node14.right = NULL;
        layer_print(&head1);
        return 0;
    }

 
4 運(yùn)行結(jié)果

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

 

 


作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)