LeetCode二叉树层序遍历出现Time Limit Exceeded错误求排查（Java）

问题描述 #

我在解决LeetCode的二叉树层序遍历问题时，用Java写的代码一直出现Time Limit Exceeded（TLE）错误，尝试排查但没解决，请求帮忙找出问题。

题目要求 #

给定二叉树的root节点，返回其节点值的层序遍历结果（从左到右、逐层遍历），返回类型为List<List<Integer>>。

• 树的节点数范围：[0,2000]
• 节点值范围：[-1000,1000]

我的代码 #

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            List<Integer> level = new ArrayList<>();
            int size = q.size();
            for(int i = 0; i < size; i++){
                level.add(q.peek().val);
                q.poll();
                if(root.left != null){
                    q.offer(root.left);
                }
                if(root.right != null){
                    q.offer(root.right);
                }
            }
            result.add(level);
        }
        return result;
    }
}

问题排查 #

代码触发TLE的核心原因是循环中始终操作原始的root节点，而非当前从队列取出的节点：

• 每次循环里，你取出队列头部节点后，却反复把root的左右子节点加入队列，而非处理当前节点的子节点；
• 这会导致队列永远无法被清空：初始加入root，后续循环不断重复添加root的左右子节点，队列元素只增不减，最终触发超时。

修正后的代码 #

只需要把操作root的逻辑改成操作当前取出的节点即可：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            List<Integer> level = new ArrayList<>();
            int size = q.size();
            for(int i = 0; i < size; i++){
                TreeNode curr = q.poll();
                level.add(curr.val);
                if(curr.left != null){
                    q.offer(curr.left);
                }
                if(curr.right != null){
                    q.offer(curr.right);
                }
            }
            result.add(level);
        }
        return result;
    }
}

关键修改点 #

• 新增TreeNode curr = q.poll();，保存当前处理的节点，同时简化peek()+poll()的分离操作；
• 将root.left、root.right替换为curr.left、curr.right，确保每次处理的是当前层节点的子节点，而非原始根节点。

内容的提问来源于stack exchange，提问作者Apoorva Walia