LeetCode 108题：Python如何用null替代None？

问题背景 #

正在做LeetCode第108题《Convert Sorted Array to Binary Search Tree》（将有序数组转换为高度平衡二叉搜索树），要求把升序整数数组转成每个节点左右子树深度差不超过1的BST。目前代码的树结构逻辑正确，但层序遍历输出存在两个问题：

• 空节点显示为None，题目要求显示null
• 输出末尾存在多余的None

输入示例：[-10,-3,0,5,9]
当前输出：[0, -3, 9, -10, None, 5, None]
期望输出：[0,-3,9,-10,null,5]

当前代码 #

from queue import Queue
from typing import Optional

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

def sortedArrayToBST(nums: [int]) -> Optional[TreeNode]:
    nbNodes = len(nums)

    if nbNodes == 1:
        root = TreeNode()
        root.val = nums[0]
        return root
    elif nbNodes == 0:
        root = TreeNode()
        root.val = None
        return root

    middle = int(nbNodes / 2)
    root = TreeNode()
    root.val = nums[middle]
    leftList = []
    rightList = []
    j = middle + 1

    for i in range(middle):
        leftList.append(nums[i])

        if j != nbNodes:
            rightList.append(nums[j])
        j += 1

    root.left = sortedArrayToBST(leftList)
    root.right = sortedArrayToBST(rightList)
    return root

def levelorder(root):
    if root==None:
        return
    Q=Queue()
    Q.put(root)
    level_order_list = []
    while(not Q.empty()):
        node=Q.get()
        if node==None:
            continue
        level_order_list.append(node.val)
        Q.put(node.left)
        Q.put(node.right)
    print(level_order_list)

if __name__ == "__main__":
    container = [-10,-3,0,5,9]
    levelorder(sortedArrayToBST(container))

问题分析与解决建议 #

1. 修正树生成函数的空节点逻辑 #

当前sortedArrayToBST中，当数组长度为0时，创建了一个val为None的TreeNode，这是错误的——空树应该直接返回None，而非一个带空值的节点。这个错误会导致遍历过程中出现多余的空节点记录。

修改点：

• 将nbNodes == 0的分支改为直接return None
• 简化节点创建，比如root = TreeNode(nums[middle])，无需先初始化再赋值val
• 优化左右子数组的生成，直接用切片nums[:middle]和nums[middle+1:]，避免手动循环拼接

2. 修正层序遍历的输出逻辑 #

当前遍历函数存在两个问题：遇到None直接跳过，没有记录空节点；没有截断末尾的多余空值。需要调整为：

• 遍历过程中，遇到None时添加'null'到列表，同时将其左右子节点（也是None）入队，但要跟踪队列中是否还有有效节点，避免无限循环
• 遍历结束后，截断列表末尾所有连续的'null'，因为题目期望输出不包含这些冗余空值

修改后的代码示例 #

from queue import Queue
from typing import Optional

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

def sortedArrayToBST(nums: [int]) -> Optional[TreeNode]:
    nbNodes = len(nums)
    if nbNodes == 0:
        return None
    if nbNodes == 1:
        return TreeNode(nums[0])
    
    middle = nbNodes // 2
    root = TreeNode(nums[middle])
    root.left = sortedArrayToBST(nums[:middle])
    root.right = sortedArrayToBST(nums[middle+1:])
    return root

def levelorder(root):
    if not root:
        print([])
        return
    
    Q = Queue()
    Q.put(root)
    level_order_list = []
    has_valid_node = True
    
    while has_valid_node and not Q.empty():
        level_size = Q.qsize()
        current_level_has_valid = False
        
        for _ in range(level_size):
            node = Q.get()
            if node:
                level_order_list.append(node.val)
                Q.put(node.left)
                Q.put(node.right)
                if node.left or node.right:
                    current_level_has_valid = True
            else:
                level_order_list.append('null')
                Q.put(None)
                Q.put(None)
        
        has_valid_node = current_level_has_valid
    
    # 截断末尾的null
    while level_order_list and level_order_list[-1] == 'null':
        level_order_list.pop()
    
    print(level_order_list)

if __name__ == "__main__":
    container = [-10,-3,0,5,9]
    levelorder(sortedArrayToBST(container))

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