Đang tải…
Đang tải…
Theo chiều rộng nhưng đảo chiều: hàng đầu trái sang phải, hàng sau phải sang trái, xoắn dần xuống dưới.
Duyệt zigzag đi theo từng tầng như BFS, nhưng đảo hướng ở mỗi hàng.
Kết quả: []
1List<List<Integer>> zigzag(Node root) {2 List<List<Integer>> out = new ArrayList<>();3 Queue<Node> q = new LinkedList<>();4 if (root != null) q.add(root);5 boolean leftToRight = true;6 while (!q.isEmpty()) {7 int size = q.size();8 List<Integer> level = new ArrayList<>();9 for (int i = 0; i < size; i++) {10 Node n = q.poll();11 level.add(n.val);12 if (n.left != null) q.add(n.left);13 if (n.right != null) q.add(n.right);14 }15 if (!leftToRight) Collections.reverse(level);16 out.add(level);17 leftToRight = !leftToRight; // đảo hướng mỗi tầng18 }19 return out;20}