面试热题（二叉树的锯齿形层次遍历）

怼烎@ 2023-10-14 17:51 10阅读 0赞

> 给你二叉树的根节点 `root` ，返回其节点值的 **锯齿形层序遍历** 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）
> 
>     输入：root = [3,9,20,null,null,15,7]
>     输出：[[3],[20,9],[15,7]]

![25f4b56ac69b402a63433170faabe79e.jpeg][]

大家一定对树的层序遍历已经能够耳熟能详了吧，这道题其实就在二叉树的层序遍历的基础上对它的结果进行了一点点的修改

![3534f922dc97400abf480e6889e84f5d.png][]

通过大家的仔细观察不难发现：是将结果集中的索引为奇数的数组进行了一次翻转，我们就可以利用模拟，它让做什么，我们就做什么的方法进行解决(树的程层序遍历是一定要会的，最好是可以进行默写甚至是进行手撕)

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> list=new ArrayList<>();
           if(root==null){
               return list;
           }
           Queue<pair> queue=new LinkedList<>();
           queue.offer(new pair(root,0));
           while(!queue.isEmpty()){
               pair pair=queue.poll();
               TreeNode node=pair.node;
               int level=pair.level;
               if(list.size()==level){
                   list.add(new ArrayList<>());
               }
               List<Integer> item=list.get(level);
               item.add(node.val);
               if(node.left!=null){
                   queue.offer(new pair(node.left,level+1));
               }
               if(node.right!=null){
                       queue.offer(new pair(node.right,level+1));
               }
           }
           return list;
           
        }
        public class pair{
            private TreeNode  node;
            private Integer level;
            public pair(TreeNode node,Integer level){
                this.level=level;
                this.node=node;
            }
        }

接下来我们对其结果数组进行操作：

for (int i = 0; i <list.size(); i++) {
                if(i%2==1){
                    Collections.reverse(list.get(i));
                }

这样的这道题就完美的结束了，一般读题的时候都想想可以用我们所熟悉的数据结构或者是模板去以出发点去进行思考，这样的话可以事半功倍

[25f4b56ac69b402a63433170faabe79e.jpeg]: https://img-blog.csdnimg.cn/img_convert/25f4b56ac69b402a63433170faabe79e.jpeg
[3534f922dc97400abf480e6889e84f5d.png]: https://img-blog.csdnimg.cn/3534f922dc97400abf480e6889e84f5d.png