将以下递归二叉树遍历算法转换为迭代算法

Question

我想了解以下递归代码是否可以通过迭代实现变得更加高效，如果可以，如何实现这样的实现。我已经有好几年没有积极编码了，所以我已经忘记了足够多的术语，我认为我无法在现有文献的帮助下自己回答这个问题。

用

l

和

r

表示我们在高度为

n

的二叉树中左转和右转的次数。假设

f(l, r)

是某个实数函数，它在常数时间内根据

l

和

r

计算某个值。假设

f

不对称，即不一定

f(l,r) = f(r,l)

。递归代码如下（Python 3中）：

def recursive_travel(l, r, cur_height, max_height):
    if cur_height == max_height:
       return f(l, r) * (f(l+1, r) + f(l, r+1))
    return recursive_travel(l+1, r, cur_height+1, max_height) + recursive_travel(l, r+1, cur_height+1, max_height)

并且最初的呼叫应该是

recursive_travel(0,0,0,n)

。迭代实现会稍微快一些，不需要递归调用，但我不知道是否有一种优雅的方法来实现这一点。所有帮助将不胜感激！

Answer 1

您可以使用动态规划来避免重新计算重叠的子问题。通过将子问题的结果存储在表中，您可以仅计算每个值一次，并在需要时重复使用它。

要减少对函数

f(i, j)

的调用次数，请预先计算值并将其存储在表中。然后每当需要特定位置

(i, j)

处的值时，请参阅该表。

def iterative_travel(n):
    # Precompute values of f(i, j) and store them in a table
    f_table = [[f(i, j) for j in range(n + 1)] for i in range(n + 1)]

    # Initialize a table to store computed values
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    # Fill the table bottom-up
    for i in range(n, -1, -1):
        for j in range(n, -1, -1):
            if i == n and j == n:
                dp[i][j] = f_table[i][j]
            elif i == n:
                dp[i][j] = dp[i][j + 1] * f_table[i][j]
            elif j == n:
                dp[i][j] = dp[i + 1][j] * f_table[i][j]
            else:
                dp[i][j] = dp[i + 1][j] * f_table[i][j] + dp[i][j + 1] * f_table[i][j]

    return dp[0][0]

这种方法确保每个唯一位置

(i, j)

仅计算一次，减少函数调用次数并提高效率。