import java.util.*;
class Solution {
public List<List<Integer>> order(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();
List<Integer> levelNodes = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
// 根据遍历方向添加节点
if (leftToRight) {
levelNodes.add(node.val);
} else {
levelNodes.add(0, node.val); // 反向插入
}
// 添加下一层节点
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(levelNodes);
leftToRight = !leftToRight; // 切换遍历方向
}
return result;
}
}
主要优化点
- 使用单队列替代双栈:
- 采用单个队列(
Queue
)来进行层次遍历,而不是使用双栈,这样可以简化代码逻辑。 - 队列用于逐层遍历节点,更符合层次遍历的特性。
- 采用单个队列(
- 在每层遍历中反向插入节点:
- 根据遍历方向选择是直接插入还是反向插入到列表中,这样可以避免额外的栈操作,同时保持锯齿形遍历的顺序。
- 利用列表初始化容量:
- 初始化
levelNodes
时指定容量,避免动态扩容的性能开销。
- 初始化
- 简化条件判断和逻辑:
- 使用
if
语句进行简单的条件切换和方向控制,使得代码更加简洁易懂。
- 使用
复杂度分析
- 时间复杂度:
O(N)
,其中N
是树中节点的数量。每个节点会被访问一次。 - 空间复杂度:
O(N)
,最坏情况下需要存储一层的节点。
通过这些优化,代码的可读性、性能和结构都得到了提升,确保了在各种情况下都能高效执行锯齿形层次遍历。