103. 二叉树的锯齿形层序遍历

比眉伴天荒 2022-08-30 04:28 158阅读 0赞

>   
> 给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
> 
> 例如：  
> 给定二叉树 \[3,9,20,null,null,15,7\]
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70][]

![20210719104755617.png][]

class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            //bfs  然后加入一个flag 控制是否将集合反向,  Collections.reverse(list);
                List<List<Integer>> res=new ArrayList();
                Deque<TreeNode> deque=new LinkedList();
                boolean flag=false;
                if(root!=null){
                    deque.add(root);
                }
                while(deque.size()>0){
                    int n=deque.size();
                    List<Integer> list=new ArrayList();
                    for(int i=0;i<n;i++){
                        TreeNode node=deque.poll();
                        list.add(node.val);
                        if(node.left!=null){
                            deque.add(node.left);
                        }
                         if(node.right!=null){
                            deque.add(node.right);
                        }
                       
                    }
                     if(flag){
                            Collections.reverse(list);
                            
                       }
                        flag=!flag;
                        res.add(list);
                }
    
                return res;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70]: /images/20220829/13c78982d6874a78bcff7c06cbb4256d.png
[20210719104755617.png]: /images/20220829/4d589519169f42efaf7238da799e01e7.png