我正在尝试使用后序遍历在 h 高度构建一个完美的二叉树。基本上我正在尝试这样做:
height = 3
numbers = list(range(1, 2 ** height))
tree = buildTree(height, numbers)
结果会是这样的:
7
3 6
1 2 4 5
我不太担心在树结构中打印出来。我只是想正确地构建树。我的代码非常简单,但我很难找出它的问题所在。
class Node:
def __init__(self, root=None):
self.root = root
self.left = self.right = None
def postorder(height, numbers):
if height == 1:
return Node(numbers.pop())
node = Node()
node.left = postorder(height-1, numbers)
node.right = postorder(height-1, numbers)
node.root = numbers.pop()
return node
最佳答案
我终于明白了。这样做的唯一方法是从右到左填充树,并在递归时递减数字。我试图从左到右填充。
def postorder(height, nums):
if h == 1:
return Node(nums.pop())
node = Node()
node.root = nums.pop()
node.right = postorder(height-1, nums)
node.left = postorder(height-1, nums)
return node
height = 3
tree = postorder(height, list(range(1, 2 ** height)))
可能值得注意的是发生了什么,因为它让我有点困惑。
一棵完美的树有 k 个元素,其中 k = (2^height) -1。 list(range(1, 2 ** height))
创建值列表,因为 range
上的停止点是唯一的。
无需反转列表以从右到左构建,因为 pop()
会从列表中删除最后一个元素。
我从左到右构建并首先填充最大的元素。
This is being built. It is being built in this order.
7 1
3 6 5 2
1 2 4 5 7 6 4 3
关于python - 使用后序遍历创建完美的二叉树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62960591/