按之字形顺序打印二叉树

按之字形顺序打印二叉树

按之字形顺序打印二叉树

• 我们可以借助队列先进先出的特性,实现层序保存!

• 然后通过flg标志位,尾插到结果数组中就是顺序打印,头插到结果数组中就实现了逆序打印!

• 注意这里通过入改变入队的顺序实现之字形不现实,做不到!!!

  

  通过记录结果时实现翻转!

 //方法一:利用队列!
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if(pRoot==null) return result;
        queue.offer(pRoot);
        boolean flg = false;//左右顺序入tmp!
        while(!queue.isEmpty()){
            int size = queue.size();
            flg = !flg;//改变打印顺序!   注意:改变入队顺序做不到
            ArrayList<Integer> tmp = new ArrayList<>();
            while(size-->0){
                TreeNode cur = queue.poll();
                if(flg){
                    //顺序打印!
                    tmp.add(cur.val);
                }else{//头插,实现逆序!
                    tmp.add(0,cur.val);
                }
                if(cur.left!=null){
                     queue.offer(cur.left);
                  }
                if(cur.right!=null){
                     queue.offer(cur.right);
                  }
            }
           if(!tmp.isEmpty()){
               result.add(tmp);
           }
        }
        return result;
    }

时间复杂度O(N),空间复杂度O(N)

• 我们刚刚想通过改变入队顺序,从而改实现反转未能实现,是由于队列是先进先出,就算改变了入队顺序,也只是改变了子树内部的反转,并没有改变全部反转
• 所以我们可以借助栈先进后出的特点实现刚刚的反转!
• 这里需要借助两个栈,一个用来

• 通过两个栈倒来倒去实现之字形打印!
• 我们将根节点入stack1,将stack1出栈并且保存,然后stack1栈中的子节点顺序入栈到stack2,利用先进后出的特点,当stack2出栈保存结果时,就实现了逆序存放!
• stack2中的节点出栈,在将其子节点按照先右后左入栈,也就实现了stack1的顺序保存!

//方法二:通过两个栈实现!
  public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if(pRoot==null) return result;
        Stack<TreeNode> stack1 = new Stack<>();
        stack1.add(pRoot);//先将根节点入栈!
        Stack<TreeNode> stack2 = new Stack<>();
        while(!stack1.isEmpty()||!stack2.isEmpty()){
            ArrayList<Integer> tmp = new ArrayList<>();
            if(!stack1.isEmpty()){
             //不为空,就将该节点的左右节点左右顺序入stack2
             //左右顺序入栈,出栈时就实现了先右后左打印!
              while(!stack1.isEmpty()){
                 TreeNode cur = stack1.pop();
                 if(cur.left!=null){
                     stack2.add(cur.left);
                 }
                 if(cur.right!=null){
                     stack2.add(cur.right);
                 }
                 tmp.add(cur.val);
             }
            }else{
             //说明stack2不为空,就将 stack2中的节点的子节点入栈到stack1
             //根据上一层的入栈顺序,先左后右,顺序入栈,就要逆序出栈,实现了逆序打印!
             //这里要实现下一层的顺序打印(顺序出栈),所以这里要逆序入栈,先右后左入栈!
               while(!stack2.isEmpty()){
                 TreeNode cur = stack2.pop();
                 if(cur.right!=null){
                     stack1.add(cur.right);
                 }
                if(cur.left!=null){
                     stack1.add(cur.left);
                 }
                 tmp.add(cur.val);
             }
            }
           if(!tmp.isEmpty()){
                result.add(tmp);
            }   
         }
        return result; 
    }