题目

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

/
9 20
/
15 7
返回锯齿形层次遍历如下：

[
[3],
[20,9],
[15,7]
]

思路

利用一个队列我们可以实现广度优先搜索，每一层的遍历的顺序都是从左到右的。如果要事项锯齿形遍历，可定义一个方向变量，表示当前的方向。根据方向不同进行头插或尾插。

代码

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        Scanner scanner = new Scanner(System.in);

        TreeNode t1 = new TreeNode(3);
        TreeNode t2 = new TreeNode(9);
        TreeNode t3 = new TreeNode(20);
        TreeNode t4 = new TreeNode(15);
        TreeNode t5 = new TreeNode(7);

        t1.left = t2;
        t1.right = t3;
        t3.left = t4;
        t3.right = t5;
        t2.left = new TreeNode(13);
        t5.right = new TreeNode(23);
        t4.left = new TreeNode(7);

        List<List<Integer>> ans = solution.zigzagLevelOrder(t1);

        for(List<Integer> l : ans) {
            for(Integer i : l) {
                System.out.print(i + ",");
            }
            System.out.println();
        }
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> answer = new LinkedList<List<Integer>>();
        if(root == null) return answer;
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int levelSize = 1;
        int direction = 0; //0: left->right    1: right -> right
        while(queue.size() > 0) {
            int newLevelSize = 0;
            LinkedList<Integer> level = new LinkedList<Integer>();

            for(int i = 0; i < levelSize; i++) {
                TreeNode t = queue.remove();
                if(t.left != null) {
                    queue.add(t.left);
                    newLevelSize++;
                }

                if(t.right != null) {
                    queue.add(t.right);
                    newLevelSize++;
                }
                
                if(direction == 1)
                    level.addFirst(t.val);
                else
                    level.add(t.val);
            }   
           //方向取反
            direction = direction ^ 1;

            levelSize = newLevelSize;
            answer.add(level);
        }

        return answer;
    }
}