c++ - 静态变量在递归中的行为

Question

我说的是 C++。 我知道如果在递归中将 int 声明为静态，则它的值不会在堆栈递归调用中重新初始化，而是使用当前值。

但是如果栈变空(或者递归计算完成)然后再次调用递归，它会使用与第一次栈调用时相同的静态值吗？？

我会详细解释我的问题。

我正在尝试以螺旋形式编写层级遍历代码。

         1
       /   \
      2     3
     / \   / \
    7  6  5  4

螺旋形式的层序遍历将得到输出 1 2 3 4 5 6 7。

void LevelSpiral(node* root, int level)
{
    static int k = level%2;
    if(root==NULL)
        return;
    if(level==1)
    {
        printf("%d ",root->val);
    }
    else
    {
        if(k==0)
        {
            LevelSpiral(root->left,level-1);
            LevelSpiral(root->right,level-1);
        }
        else
        {
            LevelSpiral(root->right,level-1);
            LevelSpiral(root->left,level-1);
        }
    }
}

void LevelOrderSpiral(node* root)
{
    for(int i=1;i<=maxheight;i++)
        LevelSpiral(root,i);
}

LevelOrderSpiral 函数对每个 i 进行单独的 LevelSpiral 调用。但在整个代码中，它始终使用 k=1(在第一个 LevelSpiral 调用中使用 i=1 初始化)并将输出打印为 1 3 2 4 5 6 7。

它不应该打印 1 2 3 4 5 6 7 因为函数堆栈为每个 i 重新初始化吗？

Answer 1

您需要一个静态变量，因为它的值要在调用之间保留，或者从一个调用到下一个递归调用。

此外，递归并不是我用于广度优先遍历的第一个工具。我会使用节点(安全)指针队列(或引用包装器或其他)。将根节点放入队列中，然后循环直到队列为空，移除前面的元素并将其所有子节点入队，然后对最近移除的元素执行您想要的操作。

关于您的实现，您在先向左和先向右之间交替。在要打印的那一行之前，级别始终等于 1，因此您总是从右到左遍历打印行。当你有一个更深的树时，你会看到更大的节点改组。在纸上画一棵示例树，并在您手写代码时在上面画出导航。