C#遍历List并移除元素时出现死循环问题求助

死循环根本原因 #

你的代码存在变量引用错误：

• 循环内已经取出了当前待处理的节点currNode，但后续判断子节点时，依旧使用的是初始化后就从未更新过的temp变量，temp永远指向根节点，导致每次循环都会重复把根节点的左节点（值2）、右节点（值3）加入队列q
• 队列q每次虽然会移除队首元素，但每次都会新增2个元素，q的长度永远不会降到0，最终触发死循环

修复方案 #

把循环里判断子节点的temp替换为刚取出的当前节点currNode即可，没用的临时变量temp可以直接删掉，修改后代码如下：

public static void ReverseLevelOrder(TreeNode root)
{
    if (root == null) return;
    List<TreeNode> q = new List<TreeNode>();
    List<TreeNode> stk = new List<TreeNode>();
    q.Add(root);
    while(q.Count > 0)
    {
        TreeNode currNode = q.ElementAt(0);
        q.RemoveAt(0);
        stk.Add(currNode);
        // 将原代码的temp替换为currNode
        if (currNode.left != null)
        {
            q.Add(currNode.left);
        }
        if (currNode.right != null)
        {
            q.Add(currNode.right);
        }
    }
   
    // 后续逆序遍历stk即可得到倒序的层序遍历结果
}

额外优化建议 #

你用List<T>实现队列的话，每次执行RemoveAt(0)的时间复杂度是O(n)，节点数量较多时性能会很差，C#内置了Queue<T>类专门适配队列场景，入队Enqueue、出队Dequeue操作的时间复杂度都是O(1)，更适合该使用场景。

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