二叉树oj-----＞二叉树的锯齿形层序遍历

﹏ヽ暗。殇╰゛Y 2023-10-02 14:35 15阅读 0赞

题目内容：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16][]

解题思路：

>  *  基本过程和层序遍历一样，在添加新节点的过程有所不同
>  *  我们定义一个标记，要求为锯齿形交替打印，因此，正常顺序打印，使用对列，在添加时，下一次使用栈即可，进行逆序，分为当 n % 2 != 0 时和 n % 2 == 0，两种情况
>  *  在进行逆序打印时，需要注意的是，当逆序打印时，进行的下一层结点的添加，也是逆序的，所以，我们需要进行再一次保存

解题代码：

class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> list = new ArrayList<>();
            if(root == null){
                return list;
            }
    
            Queue<TreeNode> q = new LinkedList<>();
            Stack<TreeNode> s = new Stack<>();
            q.offer(root);
            int n = 0;
            while(!q.isEmpty() || !s.empty()){
                List<Integer> value = new ArrayList<>();
                if(n % 2 == 0){
                    int count = q.size();
                    for(int i = 0;i < count;i++){
                        TreeNode cur = q.poll();
                        value.add(cur.val);
                        if(cur.left != null){
                            s.push(cur.left);
                        }
                        if(cur.right != null){
                            s.push(cur.right);
                        }
                    }
                    n++;
                    list.add(value);
                }else{
                    int count = s.size();
                    Stack<TreeNode> s1 = new Stack<>();
                    for(int i = 0;i < count;i++){
                        TreeNode cur = s.pop();
                        s1.push(cur);
                        value.add(cur.val);
                    }
                    for(int i = 0;i < count;i++){
                        TreeNode cur = s1.pop();
                        if(cur.left != null){
                            q.offer(cur.left);
                        }
                        if(cur.right != null){
                            q.offer(cur.right);
                        }                    
                    }
                    n++;
                    list.add(value);
                }
            }
            return list;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/3da67c515735451194668e8d7f7bdbaa.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16