[Leetcode 103]二叉树zigzag交叉遍历Binary Tree Zigzag Level Order Traversal


题目

二叉树zigzag遍历

层次遍历:始终左右

zigzag遍历:每层右左左右交替

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

分析

  • 要求输出list> ans,则先List tmp,再ans.add(tmp)
  • 写好层次遍历,用level%2余数判断所在层,每隔一层进行一次collections.reverse反转链表

代码

**注意int size=q.size(),再把size放进for循环。直接for(i;i

class Solution {
 public List> zigzagLevelOrder(TreeNode root) {
        List> ans=new ArrayList<>();
        if(root==null)
            return ans;

        Queue q=new LinkedList();
        q.add(root);

        int level=0; //zigzag新加

        while(!q.isEmpty()){
            int size=q.size();
            List tmp=new ArrayList<>();
            for(int i=0;i){
                TreeNode curNode=q.remove();
                tmp.add(curNode.val);

                if(curNode.left!=null){
                    q.add(curNode.left);
                }
                if(curNode.right!=null){
                    q.add(curNode.right);
                }
            }
            //zigzag新加
            if(level%2==1){
                Collections.reverse(tmp);
            }
            level++;

            ans.add(tmp);
        }
        return ans;
    }