1 问题
分行从上到下之字行打印二叉树
比如二叉树
23 5 1423 3 2 1 5 1 4 2 3
分行从上到下之字行打印二叉树结果如下
25 31 4 2 33 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 * 1423 *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 运行结果
25 31 4 2 33 2 4 1 5 1 2 3
