锯齿形层次遍历

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;
    }
}

主要优化点

  1. 使用单队列替代双栈
    • 采用单个队列(Queue)来进行层次遍历,而不是使用双栈,这样可以简化代码逻辑。
    • 队列用于逐层遍历节点,更符合层次遍历的特性。
  2. 在每层遍历中反向插入节点
    • 根据遍历方向选择是直接插入还是反向插入到列表中,这样可以避免额外的栈操作,同时保持锯齿形遍历的顺序。
  3. 利用列表初始化容量
    • 初始化 levelNodes 时指定容量,避免动态扩容的性能开销。
  4. 简化条件判断和逻辑
    • 使用 if 语句进行简单的条件切换和方向控制,使得代码更加简洁易懂。

复杂度分析

  • 时间复杂度O(N),其中 N 是树中节点的数量。每个节点会被访问一次。
  • 空间复杂度O(N),最坏情况下需要存储一层的节点。

通过这些优化,代码的可读性、性能和结构都得到了提升,确保了在各种情况下都能高效执行锯齿形层次遍历。

0 0 投票数
Article Rating
订阅评论
提醒
guest
0 评论
最旧
最新 最多投票
内联反馈
查看所有评论
0
希望看到您的想法,请您发表评论x