本文共 2310 字，大约阅读时间需要 7 分钟。

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

分析

思路1：之字形打印二叉树是一个类似于层序遍历的过程，根据节点所在层的不同深度，打印顺序不同。如果当前节点所在层为偶数，则是从左到右打印，如果为奇数，则从右到左打印。此处假设根节点的深度为0。

递归实现的代码（牛客AC）：

public ArrayList
   
    
      > Print(TreeNode pRoot) {        ArrayList
     
      
       > list = new ArrayList
       
        
         >(); travel(pRoot, list, 0); return list; } public void travel(TreeNode pRoot, ArrayList
         
          
           > list, int level) { if(pRoot == null) return; if(list.size() <= level) { ArrayList
           
             singleList = new ArrayList
            
             (); list.add(singleList); } ArrayList
             
               singleList = list.get(level); if((level & 1) == 0) // 深度为偶数，从左到右遍历，每次添加到list最后面 singleList.add(pRoot.val); else singleList.add(0, pRoot.val); // 深度为奇数，从右到左遍历，每次添加到list最前面 travel(pRoot.left, list, level + 1); travel(pRoot.right, list, level + 1); }
             
            
           
          
         
        
       
      
     
    
   

思路2：剑指offer中提到的思路，每次遍历一个节点时，使用两个栈结构分别存储当前层和下一层的节点，利用栈的“先入后出”的特性实现，之字形打印二叉树刚好是先入后出的，先扫描的后打印。

牛客AC：

/**     * 请实现一个函数按照之字形打印二叉树，     * 即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，     * 第三行按照从左到右的顺序打印，其他行以此类推。     *      * 方法2：使用两个栈实现     *      * @param pRoot     * @return     */    public ArrayList
   
    
     > printTreeZigzag2(TreeNode pRoot) {        ArrayList
     
      
       > list = new ArrayList
       
        
         >(); if(pRoot == null) return list; // 注意栈类型数组初始化，这种方式不能指定数组长度 // 使用两个栈分辨存储当前层和下一层的节点，两个层的顺序相反 Stack
         
          [] levels = new Stack[]{ new Stack
          
           (), new Stack<>()}; int curLevel = 0; // 当前层 int nextLevel = 1; int countLevel = 0; levels[curLevel].push(pRoot); // 任意一个栈不为空 while(!levels[0].empty() || !levels[1].empty()) { if(list.size() <= countLevel) list.add(new ArrayList
           
            ()); // 增加一个新的list，存储新的一层 ArrayList
            
              curList = list.get(countLevel); TreeNode pNode = levels[curLevel].pop(); curList.add(pNode.val); // System.out.println(pNode.val); // 打印 if(curLevel == 0) { // 当前是0层，从左到右入栈到下一层 if(pNode.left != null) levels[nextLevel].push(pNode.left); if(pNode.right != null) levels[nextLevel].push(pNode.right); } else { // 当前是1层，从右到左入栈到下一层 if(pNode.right != null) levels[nextLevel].push(pNode.right); if(pNode.left != null) levels[nextLevel].push(pNode.left); } // 当前层栈空，则进入下一层遍历 if(levels[curLevel].empty()) { countLevel++; // 层数加1 // 交换0层和1层 curLevel = 1 - curLevel; nextLevel = 1 - nextLevel; } } return list; }
            
           
          
         
        
       
      
     
    
   

参考

转载地址：http://vkxgi.baihongyu.com/