image.png

解题思路

层次遍历 广度优先搜索

  1. public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  2. List<List<Integer>> ret = new ArrayList<>();
  3. Queue<TreeNode> queue = new LinkedList<>();
  4. queue.add(root);
  5. boolean reverse = false;
  6. while (!queue.isEmpty()) {
  7. List<Integer> list = new ArrayList<>();
  8. int cnt = queue.size();
  9. while (cnt-- > 0) {
  10. TreeNode node = queue.poll();
  11. if (node == null)
  12. continue;
  13. list.add(node.val);
  14. queue.add(node.left);
  15. queue.add(node.right);
  16. }
  17. if (reverse)
  18. Collections.reverse(list);
  19. reverse = !reverse;
  20. if (list.size() != 0)
  21. ret.add(list);
  22. }
  23. return ret;
  24. }