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]
]
      

這道題是之前的：Binary Tree Level Order Traversal 的變體。

依舊用queue來實作廣度優先周遊（bfs)。

唯一的差别是不同的層次有不同的周遊順序。

奇數行是從左到右，

偶數行是從右到左。

我們用一個變量isOdd來控制目前行的周遊方向。

運作時間：

代碼：

public class BinaryTreeZigzagLevelOrderTraversal {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> store = new LinkedList<>();
        store.add(root);
        int len = store.size();// the node of same level
        List<Integer> curList = new LinkedList<>();
        boolean isOdd = true;
        while (!store.isEmpty()) {
            TreeNode temp = store.poll();
            if (isOdd) {
                curList.add(temp.val);
            } else {
                curList.add(0, temp.val);
            }
            if (temp.left != null) {
                store.add(temp.left);
            }
            if (temp.right != null) {
                store.add(temp.right);
            }
            len--;
            if (len == 0) {
                len = store.size();
                result.add(new LinkedList<>(curList));
                curList = new LinkedList<>();
                isOdd = !isOdd;
            }
        }
        return result;
    }
}