Python实现TreeNode类方法将有序列表转为平衡BST并输出前序遍历

核心问题点 #

• 原代码中srt递归函数没有返回构造完成的TreeNode对象，且直接将子列表片段传入TreeNode构造函数，导致左右子节点的val属性直接存储了整个子列表，而非列表对应的节点值，这是输出中出现子列表的直接原因。
• 嵌套的srt函数始终修改的是外层根节点的left、right属性，没有为子树单独创建和构造TreeNode实例，递归逻辑完全错误，这也是修改后仅返回根节点值的核心原因。
• 原srt函数没有为子节点递归调用构造逻辑，子树的结构完全没有生成。

修复后的完整代码 #

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

    def sorted_array_to_bst(self, nums):
        def srt(sub_nums):
            if not sub_nums:
                return None
            mid = len(sub_nums) // 2
            # 新建当前子树的根节点
            node = TreeNode(sub_nums[mid])
            # 递归构造左右子树
            node.left = srt(sub_nums[:mid])
            node.right = srt(sub_nums[mid+1:])
            return node
        
        if not nums:
            return
        # 用递归构造完成的根节点属性覆盖当前实例
        root = srt(nums)
        self.val = root.val
        self.left = root.left
        self.right = root.right

    def preorder(self, val):
        if self.val is not None:
            val.append(self.val)
        if self.left is not None:
            self.left.preorder(val)
        if self.right is not None:
            self.right.preorder(val)
        return val

# 测试
node = TreeNode()
some_list = [1, 2, 3, 4, 5, 6, 7]
node.sorted_array_to_bst(some_list)
print(node.preorder([]))

代码说明 #

修复后的代码严格符合要求的约束：

1. sorted_array_to_bst是TreeNode类的成员方法
2. 方法入参为完整的有序列表，而非单个元素
   运行上述代码输出结果为[4, 2, 1, 3, 6, 5, 7]，和预期结果完全一致。

内容的提问来源于stack exchange，提问作者lukasz21