Skip to main content
 首页 » 编程设计

python之如何将这种在二叉树中的两个级别之间查找节点的递归实现转换为迭代版本

2025年05月04日7unruledboy

这就是我构建二叉树的方式:

class BinaryTree(): 
    def __init__(self, value): 
        self.key = value 
        self.left = None 
        self.right = None 
 
t2 = BinaryTree(20) 
t2.left = BinaryTree(8) 
t2.left.left = BinaryTree(4) 
t2.left.right = BinaryTree(12) 
t2.left.right.left = BinaryTree(10) 
t2.left.right.right = BinaryTree(14) 
t2.right = BinaryTree(22) 

这是我的递归函数,它返回两个级别之间的节点:

def find_nodes_between_two_levels(tree, high, low, currentLevel=1, output=None): 
    if output is None: 
        output = {} 
 
    if tree is None or currentLevel > low: 
        return 
 
    if currentLevel >=high and currentLevel<=low: 
        if currentLevel not in output: 
            output[currentLevel] = [tree.key] 
        else: 
            output[currentLevel].append(tree.key) 
    nextLevel = currentLevel + 1 
    find_nodes_between_two_levels(tree.left, high, low, nextLevel, output) 
    find_nodes_between_two_levels(tree.right, high, low, nextLevel, output) 
 
    return output 

这是一个输出:

print find_nodes_between_two_levels(t2, 2, 4) 
{2: [8, 22], 3: [4, 12], 4: [10, 14]} 

这个问题的迭代解决方案是什么?

请您参考如下方法:

由于此函数不是尾递归的,因此迭代解决方案将需要通过堆栈或队列维护您自己的状态。就我个人而言,对于此类问题,我可能会使用队列方法并对树进行广度优先遍历。

def find_nodes_between_two_levels(root, high, low): 
    from collections import defaultdict 
    output = defaultdict(list) 
    queue = [(root, 1)] 
    while queue: 
        tree, level = queue.pop() 
        if not tree or level > low: 
            continue 
        if high <= level <= low: 
            output[level].append(tree.key) 
        level += 1 
        queue.append((tree.left, level)) 
        queue.append((tree.right, level)) 
    return output 

我留下了你原来的意思high和 low , 但这些自 high < low 以来有些困惑.

这个答案的重要部分是了解递归和迭代解决方案之间的关系。在结构上,它们非常相似。关键观察结果是,状态现在以显式 queue 方式维护,而不是使用隐式堆栈来维护状态。 .每个以前的递归调用现在都变成了 append调用 queue .上一个output参数现在可以成为局部变量,因为没有递归调用来跟踪状态。同样,high和 low不需要维护参数,因为它们在递归调用中是不可变的。