BM27 按之字形顺序打印二叉树

淡淡的烟草味﹌ 2023-10-04 17:42 9阅读 0赞

### 描述 ###

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

数据范围：0≤n≤1500,树上每个节点的val满足 ∣val∣<=1500  
要求：空间复杂度：O(n)，时间复杂度：O(n)

例如：  
给定的二叉树是\{1,2,3,\#,\#,4,5\}

![4f1a59d58cbbc513b4b7a4685513d619.png][]

该二叉树之字形层序遍历的结果是

\[1\],

\[3,2\],

\[4,5\]

### 示例1 ###

输入：

{1,2,3,#,#,4,5}

返回值：

[[1],[3,2],[4,5]]

说明：

如题面解释，第一层是根节点，从左到右打印结果，第二层从右到左，第三层从左到右。

### 示例2 ###

输入：

{8,6,10,5,7,9,11}

返回值：

[[8],[10,6],[5,7,9,11]]

### 示例3 ###

输入：

{1,2,3,4,5}

返回值：

[[1],[3,2],[4,5]]

##  ##

## 方法一(层序遍历) ##

层序遍历的模板只要加一个变量记录层数，然后如果奇数层就把奇数层的节点值加入到总的列表中；如果是偶数层，则先把偶数层的所有节点值倒转后加入到总的列表中

## 方法 二（两个栈进行交替进出） ##

可以联想到**栈的「先入后出」的特性**。由于栈仅能在一端进行入栈出栈操作，因此需要定义两个栈，交替使用。

步骤如下（如图所示）：

1.  定义两个栈stk1，stk2；将根结点入栈stk1；
2.  对于下一层，应是「从右至左」打印，因此需要遍历栈stk1、访问每一个元素，存储这一层的所有节点的值，并将每一元素的孩子按照「先左孩子、后右孩子」的顺序入栈stk2；将访问的结点保存；
3.  对于下一层，应是「从左至右」打印，因此需要遍历栈stk2、访问每一个元素，存储这一层的所有节点的值，并将每一元素的孩子按照「先右孩子、后左孩子」的顺序入栈stk1；将访问的结点保存；
4.  重复上述操作，直至两个栈全为空。

![cb2f480b4b9b0a2c54b894a309c1126b.png][]

import java.util.ArrayList;
    import java.util.Deque;
    import java.util.*;
    
    /*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
            ArrayList<ArrayList<Integer>> al=new ArrayList<>();
            if(pRoot==null){
                 return al;
             }
            //定义两个栈，进行交替，来实现奇数层和偶数层
            Stack<TreeNode> s1=new Stack<>();
            Stack<TreeNode> s2=new Stack<>();
            s1.add(pRoot);
            while(!s1.empty()||!s2.empty()){  //两栈都为空就停止循环
                //两个栈交替进出栈
                ArrayList<Integer> list=new ArrayList<>();
                while(!s1.empty()){  //当第一个栈不为空时
                   TreeNode temp=s1.pop();  //出栈并返回栈顶元素
                    list.add(temp.val);
                    if(temp.left!=null){  //这样做是为了保证该元素下一层的访问是右-》左
                        //该元素的左子树先进，右子树后进栈2中
                        s2.push(temp.left);
                    }
                    if(temp.right!=null){
                        s2.push(temp.right);
                    }
                }
                if(!list.isEmpty()){  //如果这一层不为空
                     al.add(list);  //则将这一层的所有节点值加入到总的列表中
                }
                 //清除上一层列表的值，为下一层做准备
                //list.clear();   //不能直接用list.clear，这样做会把前面的奇数层节点的值也删除调，所以这里我重新创建一个列表
                //来存储下一层的节点值（偶数层）
                 ArrayList<Integer> list2=new ArrayList<>();
                //这一层遍历完了
                while(!s2.empty()){//这是下一层即偶数层
                    TreeNode temp=s2.pop();  //出栈
                    list2.add(temp.val);  //将该节点值加入到列表中
                    if(temp.right!=null){  //保证下一层的访问是左-》右
                        s1.push(temp.right);
                    }
                    if(temp.left!=null){
                        s1.push(temp.left);
                    }
                }
                if(!list2.isEmpty()){  //如果这一层不为空
                    al.add(list2);   //则将这一层的所有节点值加入到总的列表中
                }
             }
            return al;
        }
    }

[4f1a59d58cbbc513b4b7a4685513d619.png]: https://img-blog.csdnimg.cn/img_convert/4f1a59d58cbbc513b4b7a4685513d619.png
[cb2f480b4b9b0a2c54b894a309c1126b.png]: https://img-blog.csdnimg.cn/img_convert/cb2f480b4b9b0a2c54b894a309c1126b.png