Java 链表 求二叉树的锯齿层遍历 LinkedList用法 面试、笔试 高频知识点 Leetcode_java linkedlist遍历二叉树

话不多说，直接上代码：

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // 创建一个链表，存储最终结果
        List<List<Integer>> ans = new LinkedList<List<Integer>>();
        if(root == null){
            return null;
        }
        // 队列，用来层次遍历节点
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        // isOrderLeft 这个用来判断遍历每层的方向，从左到右
        // 基数层是从左往右(根节点是从0层开始), 偶数层是从右往左移动
        boolean isOrderLeft = true;
        
 
        while(!queue.isEmpty()){
            // 用来存储每一层的节点
            Deque<Integer> deque = new LinkedList<Integer>();
            int size = queue.size();
            
            for(int i = 0; i < size; i++){
                TreeNode currNode = queue.poll();
                if(isOrderLeft){
                    deque.addLast(currNode.val);
                }else{
                    deque.addFirst(currNode.val);
                }
                if(currNode.left != null){
                    queue.offer(currNode.left);
                }
                if(currNode.right != null){
                    queue.offer(currNode.right);
                }
            }
            ans.add(new LinkedList<Integer>(deque));
            isOrderLeft = !isOrderLeft;
        }
        return ans;
    }
}