今天的題目為103.Binary Tree Zigzag Level Order Traversal,題目一樣再叫我們讀一顆二元數,但root步算,第一層是從右到左讀取,第二層則是從左到右讀取
以下為程式碼以及解說:
import java.util.*;
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>> result = new ArrayList<>(); // 儲存最終結果
if (root == null) return result; // 若根節點為空,直接回傳空列表
Queue<TreeNode> queue = new LinkedList<>(); // 用來進行層序遍歷的佇列
queue.offer(root);
boolean leftToRight = true; // 控制每層的遍歷方向
while (!queue.isEmpty()) {
int size = queue.size(); // 當前層的節點數量
LinkedList<Integer> level = new LinkedList<>(); // 使用 LinkedList 方便頭尾插入
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll(); // 取出當前層的節點
// 根據方向插入節點值
if (leftToRight) {
level.addLast(node.val); // 從尾部加入(正常順序)
} else {
level.addFirst(node.val); // 從頭部加入(反向順序)
}
// 加入下一層的左右子節點
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level); // 將當前層結果加入最終結果
leftToRight = !leftToRight; // 每層切換方向
}
return result;
}
}
今天的相對比較難一些,我覺得是因為要做一個換邊的動作的關係。