二叉树广度优先遍历问题：左下角节点无法正常遍历

我尝试遍历一棵二叉树结构，但在遍历左下角节点时遇到问题。二叉树结构示意图如下：

以下是相关代码，我认为它接近解决方案，但存在一处小问题：当要遍历左下角节点时，foo函数中low等于high，导致该节点无法被遍历。

private State? BFS()
{
    State state = new State();
    foo(0, items.Count, state);
    return bestState;
}

private void foo(int low, int high, State state)
{
    int lCount = low;

    while (lCount < high)
    {
        State newState = new State(items[lCount++], state);
        if (predicate(newState))
        {
            bestState = newState;
        }
        queue.Enqueue(newState);
    }
    while(low < high)
    {
        foo(++low, high, queue.Dequeue());
    }
}

问题修复 #

问题根源在于第二个while循环中递归调用时提前递增了low，导致传入子调用的low直接等于high，此时子调用里的第一个while(lCount < high)循环会直接跳过，左下角节点的逻辑完全没执行。

修改第二个while循环的逻辑，将++low的操作从递归参数中移出，改为循环末尾手动递增：

private void foo(int low, int high, State state)
{
    int lCount = low;

    while (lCount < high)
    {
        State newState = new State(items[lCount++], state);
        if (predicate(newState))
        {
            bestState = newState;
        }
        queue.Enqueue(newState);
    }
    int currentLow = low;
    while(currentLow < high)
    {
        foo(currentLow + 1, high, queue.Dequeue());
        currentLow++;
    }
}

或者更简洁的写法：

while(low < high)
{
    foo(low + 1, high, queue.Dequeue());
    low++;
}

这样每次递归传入的low是当前low+1，而不是提前修改原变量，确保子调用的low始终小于high（只要当前循环条件满足），左下角节点就能被正常遍历处理。

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