如何从先序树遍历生成的数组重建二叉树

Question

我被要求实现一个前序树遍历函数，该函数应该返回一个表示树的数组， 然后我被要求实现一个函数，从我之前的函数返回的数组中重建树。 就像从一台电脑发送一棵二叉树，然后在接收端接收并重建它一样。 重要的是数据只能传输一次，所以我不能使用标准的预序和中序组合。

在我的解决方案中，每个节点都会被打印，然后添加到包含所有打印节点的数组中，如果节点没有左子树，它将打印并添加字母“L”，如果树没有没有右子树，它将打印并将字母“R”添加到数组中。

那部分很简单，但是，我不知道如何在接收端重建树。 任何帮助或想法将非常感激。

这是我为发送部分所做的事情：

class TreeNode(object):
"""This class represents a tree."""

    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def send(arr_tree, data):
    print(data)
    arr_tree.append(data)

def send_sub_tree(arr_tree, node):
    send(arr_tree, node.data)
    if node.left is None:
        send(arr_tree, "L")
    else:
        send_sub_tree(arr_tree, node.left)
    if node.right is None:
        send(arr_tree, "R")
    else:
        send_sub_tree(arr_tree, node.right)

if __name__ == '__main__':
    tree = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, 
    TreeNode(6), TreeNode(7)))
    received_tree = []
    send_sub_tree(received_tree, tree)
    reconstructed_tree = reconstruct_tree(received_tree)

编辑：

我已经设法实现了一些可行的东西，但它很混乱并且不能完美地重建发送的部分：

def reconstruct_tree(arr_tree):
    node = TreeNode(arr_tree[0])
    print(node.data)

    if arr_tree[1] == "L" and arr_tree[2] == "R":
        if len(arr_tree) > 3 and arr_tree[3] != "L" and arr_tree[3] != "R":
            node.right = reconstruct_tree(arr_tree[3:])

    else:
        return node
    if arr_tree[1] != "L":
        node.left = reconstruct_tree(arr_tree[1:])
        return node

return node

Answer 1

您可以按照以下方法进行操作。我还将您的函数移到类中，重命名它们，并进行了一些修改：

class TreeNode(object):
    """This class represents a tree."""
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def to_list(self):
        return [self.data] + (
                self.left.to_list() if self.left else ["L"]
            ) + (
                self.right.to_list() if self.right else ["R"]
            )
    
    @staticmethod
    def from_list(lst):
        def recurse(it):
            try:
                data = next(it)
            except StopIteration: # Only happens if list is incomplete
                return
            if data == 'L' or data == 'R':
                return
            return TreeNode(data, recurse(it), recurse(it))
        return recurse(iter(lst))

tree = TreeNode(1, 
            TreeNode(2, 
                TreeNode(4),
                TreeNode(5)
            ), 
            TreeNode(3, 
                TreeNode(6),
                TreeNode(7)
            )
        )
lst = tree.to_list()
print(lst)
# Reverse operation
recovered_tree = TreeNode.from_list(lst)
# Make that a list again to see if it is the same tree
lst2 = recovered_tree.to_list()
print(lst2) # Same as lst

请注意，您也可以使用“L”表示右侧子级，或使用“R”表示左侧子级，因为数组中的位置已经明确表明要使用哪个子级。一个特殊符号就足够了。

Answer 2

让我们考虑一个通用算法，使用维基百科的前序遍历示例：

F, B, A, D, C, E, G, I, H.

让我们为空子树标记

None

：

A = [F, B, A, None, None, D, C, None, None, E, None, None, G, None, I, H, None]

现在我们从根源开始：

F
-> have a left subtree so insert B
   descend
-> have a left subtree so insert A
   descend
-> have no left subtree
-> have no right subtree
   return
-> have a right subtree so insert D
   descend
-> have a left subtree so insert C
   descend
-> have no left subtree
-> have no right subtree
   return
-> have a right subtree so insert E
   descend
-> have no left subtree
-> have no right subtree
   return

但是我们如何知道我们返回到哪个索引和节点呢？一种方法是从返回要使用的下一个索引的节点调用递归函数（请记住此处和后面的示例中

i

是局部变量）：

f(node, i):
  # left subtree
  if A[i]:
    insertLeft(A[i])
    i = f(node.left, i + 1)
  else:
    i = i + 1

  #right subtree
  if A[i]:
    insertRight(A[i])
    i = f(node.right, i + 1)
  else
    i = i + 1

  return i

让我们应用到我们的例子：

A = [F, B, A, None, None, D, C, None, None, E, None, None, G, None, I, H, None]

f(F, 1)
  insertLeft(B)

  i = f(B,2)
        insertLeft(A)

        i = f(A,3)
              i = 4
              i = 5
              return 5

        insertRight(D)

        i = f(D,6)
              insertLeft(C)

              i = f(C,7)
                    i = 8
                    i = 9
                    return 9

              insertRight(E)

              i = f(C,10)
                    i = 11
                    i = 12
                    return 12

              return 12

        return 12

  insertRight(G)  # A[12]

  etc...