python - 使用后序遍历创建完美的二叉树

Question

我正在尝试使用后序遍历在 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

Answer 1

我终于明白了。这样做的唯一方法是从右到左填充树，并在递归时递减数字。我试图从左到右填充。

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