2024.2.16力扣每日一题——二叉树的锯齿形层序遍历

2024.2.16

• • • 题目来源
    • 我的题解
    • • 方法一 双端队列+标志

题目来源

力扣每日一题；题序：103

我的题解

方法一 双端队列+标志

层序遍历 利用双端队列和标志，判断当前应该往那个方向遍历
注意：在逆向遍历时，加入后续节点到队列中的顺序需要改变

时间复杂度：O(N)，其中 N 为二叉树的节点数。每个节点会且仅会被遍历一次。
空间复杂度：O(N)。需要维护存储节点的队列和存储节点值的双端队列，空间复杂度为 O(N)。

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res=new ArrayList<>();
    if(root==null)
        return res;
    LinkedList<TreeNode> queue=new LinkedList<>();
    queue.addFirst(root);
    boolean flag=false;//false表示从右到左，true表示从左到右
    while(!queue.isEmpty()){
        int sz=queue.size();
        List<Integer> list=new ArrayList<>();
        for(int i=0;i<sz;i++){
            //从右到左
            if(!flag){
                TreeNode t=queue.pollLast();
                list.add(t.val);
                if(t.left!=null)
                    queue.addFirst(t.left);
                if(t.right!=null)
                    queue.addFirst(t.right);
            //从左到右
            }else{
                TreeNode t=queue.pollFirst();
                list.add(t.val);
                //注意存入的顺序需要改变
                if(t.right!=null)
                    queue.addLast(t.right);
                if(t.left!=null)
                    queue.addLast(t.left);
                
                
            }
        }
        flag=!flag;
        res.add(list);
    }
    return res;
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈