为什么我在leetcode中的二叉树级别顺序遍历问题中遇到“超出时间限制”错误？

Question

我正在尝试解决问题：LeetCode 上的二叉树级别顺序遍历问题，我也尝试寻找答案，但我仍然收到超出时间限制（TLE）错误。请帮我找出问题所在。我正在使用Java来解决这个问题。

给定二叉树的

root

，返回其节点值的层序遍历。 （即从左到右，逐级）。

示例1：

输入：

root = [3,9,20,null,null,15,7]

输出：

[[3],[9,20],[15,7]]

示例2：

输入：

root = [1]

输出：

[[1]]

示例3：

输入：

root = []

输出：

[]

限制：

• 树中的节点数在

  [0, 2000]

  范围内。

• -1000 <= Node.val <= 1000

我们必须以

List<List<Integer>>

的形式返回级别顺序遍历。

这是我针对同一问题的代码：

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

Answer 1

简短回答：

原因是因为你的代码中存在一个逻辑错误导致了无限循环，你使用的是根节点而不是队列中正在处理的当前节点，这导致不断地将相同的子节点添加回队列中，导致无限循环。

说明：

您的代码：

while(!q.isEmpty()){ //here we say as long as the queue is not empty keep looping
            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); //here we add root left
                }
                if(root.right != null){
                    q.offer(root.right); //here we add root right
                }
                //so in result the loop every time will add the root left and right causing an infinite loop
            }
            result.add(level);
        }
        return result;
    }

正如您在代码中看到的那样，即使您修复了无限循环，它在逻辑上仍然是错误的，为什么您每次都要检查

root

左右而不是设置一个在树上移动的指针？作为解决方案，您可以使用

current

节点，并且当您遍历树时该节点必须更改。

解决方案代码

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 current = q.poll(); //here we make current
                level.add(current.val);
                
                if (current.left != null) { //here we check current left
                    q.offer(current.left); 
                }
                if (current.right != null) { //here we check current right
                    q.offer(current.right);
                }
            }
            result.add(level);
        }

        return result;
    }
}

注意此代码仅修复您的算法，但是有更好的方法来解决此问题和更好的代码风格，请检查人们所做的提交以向他们学习。