剑指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
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/90323911