Binary Tree Zigzag Level Order Traversal

二叉树锯齿形层次遍历

题目

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

For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

解析重点

1.类似与广度优先遍历，我们需要把一层的数据放一起，那么我们怎么把一层的数据放一起呢，我们可以使用一个标志，当递归每加一层时，标志加一，标志相同点放在同一层list里面。
2.我们需要锯齿形的遍历，那么对于偶数层的数据我们添加list的时候可以反向添加，这样就保证了偶数层的数据从右边开始。

java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) 
    {
        List<List<Integer>> sol = new ArrayList<>();
        travel(root, sol, 0);
        return sol;
    }
    
    //curr当前节点，sol每层的list，level当前所处的层次
    private void travel(TreeNode curr, List<List<Integer>> sol, int level)
    {
        if(curr == null) return;
        
        if(sol.size() <= level)//如果第level层没有创建list，则创建list
        {
            List<Integer> newLevel = new LinkedList<>();
            sol.add(newLevel);
        }
        
        List<Integer> collection  = sol.get(level);
        if(level % 2 == 0) collection.add(curr.val);//奇数层正常遍历
        else collection.add(0, curr.val);//偶数层反向遍历
        
        travel(curr.left, sol, level + 1);//递归计算
        travel(curr.right, sol, level + 1);
    }
}