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

1 问题

分行从上到下之字行打印二叉树

比如二叉树

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

分行从上到下之字行打印二叉树结果如下

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

2 分析

这里我们可以用2个栈（先进后出），先把stack1push根节点，然后把stack全部弹出来，分别push根节点的左节点和右节点到stack2，然后stack2弹出栈里面的每个节点，我们分别把每个节点的右节点和左节点push到stack1,里面去，直到stack1和stack2都是空元素结束循环。

3 代码实现

#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 运行结果

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