leetcode--103. 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],

return its zigzag level order traversal as:

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

2、边界条件:root == null

3、思路：广度优先遍历BFS，只不过遍历过程中会变换一下顺序，用stack实现。双stack实现倒序。这是改变遍历的顺序。

还有一种思路是改变保存结果的顺序。

4、代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> results = new ArrayList<>();
        if (root == null) {
            return results;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        stack1.push(root);
        int ctrl = 0;
        int curLevelNum = 1;
        while (!stack1.isEmpty()) {
            List<Integer> result = new ArrayList<>();
            Stack<TreeNode> stack2 = new Stack<>();
            int nextLevelNum = 0;
            while (curLevelNum-- > 0) {
                TreeNode top = stack1.pop();
                result.add(top.val);
                if (ctrl % 2 == 0) {
                    if (top.left != null) {
                        stack2.push(top.left);
                        nextLevelNum++;
                    }
                    if (top.right != null) {
                        stack2.push(top.right);
                        nextLevelNum++;
                    }
                } else {
                    if (top.right != null) {
                        stack2.push(top.right);
                        nextLevelNum++;
                    }
                    if (top.left != null) {
                        stack2.push(top.left);
                        nextLevelNum++;
                    }
                }
            }
            ctrl++;
            curLevelNum = nextLevelNum;
            stack1 = stack2;
            results.add(result);
        }
        return results;
    }
}

5、api