这就是我构建二叉树的方式:
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不需要维护参数,因为它们在递归调用中是不可变的。
