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