递归转非递归

1.先序dfs转非递归—树的先序非递归

void fun(int n) 
{
    if (n < 10)
    {
        cout << n * 10 + n;
        return;
    }

    fun(n / 10);
    fun(n % 10);
}

// 非递归
void fun(int n)
{
    stack<int> s;
    s.push(n);
    while (!s.empty())
    {
        int t = s.top();
        s.pop();

        if (t < 10)
            cout << t * 10 + t;
        else
        {
            int a = t / 10, b = t % 10;
            s.push(b);
            s.push(a);
        }
    }
} 

2.后序dfs转非递归—递归栈调用

思路：如上图分析工作栈变化可知，将f(4),f(3),f(2),f(1)入栈，然后依次出栈，计算后再入栈

int fun(int n) 
{
    if (n < 10)
        return n * 10 + n;

    int a = fun(n / 10);
    int b = fun(n % 10);

    return a * 100 + b;
}

int fun(int n)
{
    stack<int> s;
    // f(4),f(3),f(2),f(1)依次入栈
    while (n)
    {
        int t = n % 10;
        t = t * 10 + t;
        s.push(t);
        n /= 10;
    }

    // 计算
    while (s.size() > 1)
    {
        int a = s.top();
        s.pop();
        int b = s.top();
        s.pop();
        s.push(100 * a + b);
    }

    return s.top();
}