Z字型遍历二叉树

编码过程

1. 掏出Deque，先写从左往右遍历

class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {Deque<TreeNode> deque = new ArrayDeque<>();deque.offer(root);while (!deque.isEmpty()) {int n = deque.size();for (int i = 0; i < n; ++i) {TreeNode e = deque.pollFirst();if (e.left != null) {deque.offerLast(e.left);}if (e.right != null) {deque.offLast(e.right);}}}}
}

2. 再写倒着遍历

class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {Deque<TreeNode> deque = new ArrayDeque<>();deque.offer(root);while (!deque.isEmpty()) {int n = deque.size();for (int i = 0; i < n; ++i) {TreeNode e = deque.pollFirst();if (e.left != null) {deque.offerLast(e.left);}if (e.right != null) {deque.offLast(e.right);}}for (int i = 0; i < n; ++i) {TreeNode e = deque.pollLast();if (e.right != null) {deque.offerFirst(e.right);}if (e.left != null) {deque.offerFirst(e.left);}}}}
}

到此，核心代码写完了，剩下的都是缝缝补补了。核心代码就一点：入队的时候左孩子在左边，右孩子在右边。这样，从右边出队就是从右往左倒序遍历，从左边出队就是从左往右正序遍历。
3. 区分当前层是从左往右还是从右往左。加个布尔变量或者整数变量分奇偶都行。

class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {Deque<TreeNode> deque = new ArrayDeque<>();deque.offer(root);int depth = 0;while (!deque.isEmpty()) {int n = deque.size();if (depth % 2 == 0) {for (int i = 0; i < n; ++i) {TreeNode e = deque.pollFirst();if (e.left != null) {deque.offerLast(e.left);}if (e.right != null) {deque.offLast(e.right);}}} else {for (int i = 0; i < n; ++i) {TreeNode e = deque.pollLast();if (e.right != null) {deque.offerFirst(e.right);}if (e.left != null) {deque.offerFirst(e.left);}}}depth++;}}
}

4. 存结果

class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) {return res;}Deque<TreeNode> deque = new ArrayDeque<>();deque.offer(root);int depth = 0;while (!deque.isEmpty()) {List<Integer> level = new ArrayList<>();int n = deque.size();if (depth % 2 == 0) {for (int i = 0; i < n; ++i) {TreeNode e = deque.pollFirst();level.add(e.val);if (e.left != null) {deque.offerLast(e.left);}if (e.right != null) {deque.offerLast(e.right);}}} else {for (int i = 0; i < n; ++i) {TreeNode e = deque.pollLast();level.add(e.val);if (e.right != null) {deque.offerFirst(e.right);}if (e.left != null) {deque.offerFirst(e.left);}}}depth++;res.add(level);}return res;}
}

5. 稍微重构一下

class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) {return res;}Deque<TreeNode> deque = new ArrayDeque<>();deque.offer(root);int depth = 0;while (!deque.isEmpty()) {List<Integer> level = new ArrayList<>();int n = deque.size();for (int i = 0; i < n; ++i) {if (depth % 2 == 0) {TreeNode e = deque.pollFirst();level.add(e.val);if (e.left != null) {deque.offerLast(e.left);}if (e.right != null) {deque.offerLast(e.right);}} else {TreeNode e = deque.pollLast();level.add(e.val);if (e.right != null) {deque.offerFirst(e.right);}if (e.left != null) {deque.offerFirst(e.left);}}}depth++;res.add(level);}return res;}
}

欧了