从 Python 列表构建二叉树

Question

假设我有以下二叉树：

以及以下TreeNode定义：

class TreeNode:
    def __init__(self, x, left: = None, right: = None):
        self.val = x
        self.left = left
        self.right = right

为了构建这棵树，我目前需要编写以下代码：

def build_tree() -> TreeNode:
    node0 = TreeNode(2, left=TreeNode(4), right=TreeNode(5))
    node1 = TreeNode(3, right=TreeNode(7))
    root = TreeNode(1, left=node0, right=node1)
    return root

这对于大树来说效率非常低。Leetcode 为我提供了 Python 列表形式的树。对于上面的例子，它写道：

[1, 2, 3, 4, 5, None, 7]

我很想重构，build_tree所以它需要一个列表，构建树并返回根节点：

def build_tree(values: list) -> ListNode:
    ...

关于如何创建这个功能有什么想法吗？

这是一个更复杂的例子：

[4, 6, 2, None, 5, 1, 9, 2, 1, 3, 4, None, 7]

Answer 1

您可以像这样重构代码。它将采用数字或字符串列表并构建 BST，但对于简单的二叉树，只if需要删除一个条件。

def add_child(self, val):
    if val == self.val:
        return
    
    elif val < self.val:
        if self.left:
            self.left.add_child(val)
        else:
            self.left = BinarySearchTree(val)
    else:
        if self.right:
            self.right.add_child(val)
        else:
            self.right = BinarySearchTree(val)

def build_tree(elements):
     root = BinarySearchTree(elements[0])
     for i in range(1, len(elements)):
         root.add_child(elements[i])

     return root

if __name__=="__main__":
     numbers = [15, 10, 8, 12, 20, 16, 25]        
     root = build_tree(numbers)