Binary Tree

class TreeNode:
    """二叉树节点类"""
    def __init__(self, val: int):
        self.val: int = val                # 节点的值
        self.left: 'TreeNode' | None = None  # 左子节点，初始为 None
        self.right: 'TreeNode' | None = None # 右子节点，初始为 None

def display(root):
    """打印二叉树为字符树"""
    lines, *_ = _display_aux(root)  # 调用辅助函数，获取打印所需的行列表
    for line in lines:
        print(line)  # 逐行打印

def _display_aux(node):
    """
    辅助递归函数，返回表示二叉树的字符串行列表，以及子树的宽度、高度和根节点在宽度中的偏移量
    """
    if node is None:
        # 如果节点为空，返回一个空格，占位
        return [" "], 0, 0, 0

    line = f'{node.val}'  # 将节点的值转换为字符串
    width = len(line)     # 当前行的宽度，即节点值的字符数
    height = 1            # 当前子树的高度，初始为 1
    middle = width // 2   # 根节点在当前行中的中间位置

    # 情况 1：只有左子树
    if node.left and not node.right:
        l_lines, l_width, l_height, l_middle = _display_aux(node.left)  # 递归左子树
        # 第一行：在左子树上方添加连接线，连接到当前节点
        first_line = ' ' * (l_middle + 1) + '_' * (l_width - l_middle - 1) + line
        # 第二行：在左子树和当前节点之间添加斜杠，表示连接
        second_line = ' ' * l_middle + '/' + ' ' * (l_width - l_middle - 1 + width)
        # 调整左子树的行，使其右移，和当前节点对齐
        shifted_lines = [line + ' ' * width for line in l_lines]
        # 返回合并后的行列表，更新宽度和高度信息
        return [first_line, second_line] + shifted_lines, l_width + width, l_height + 2, l_width + width // 2

    # 情况 2：只有右子树
    if not node.left and node.right:
        r_lines, r_width, r_height, r_middle = _display_aux(node.right)  # 递归右子树
        # 第一行：在当前节点后添加连接线，连接到右子树
        first_line = line + '_' * r_middle + ' ' * (r_width - r_middle)
        # 第二行：在当前节点和右子树之间添加反斜杠，表示连接
        second_line = ' ' * (width + r_middle) + '\\' + ' ' * (r_width - r_middle - 1)
        # 调整右子树的行，使其左移，和当前节点对齐
        shifted_lines = [' ' * width + line for line in r_lines]
        # 返回合并后的行列表，更新宽度和高度信息
        return [first_line, second_line] + shifted_lines, width + r_width, r_height + 2, width // 2

    # 情况 3：同时有左、右子树
    if node.left and node.right:
        l_lines, l_width, l_height, l_middle = _display_aux(node.left)   # 递归左子树
        r_lines, r_width, r_height, r_middle = _display_aux(node.right)  # 递归右子树
        # 第一行：连接左子树、当前节点和右子树的连接线
        first_line = ' ' * (l_middle + 1) + '_' * (l_width - l_middle - 1) + line + '_' * r_middle + ' ' * (r_width - r_middle)
        # 第二行：在左子树和当前节点之间添加斜杠，在当前节点和右子树之间添加反斜杠
        second_line = ' ' * l_middle + '/' + ' ' * (l_width - l_middle - 1 + width + r_middle) + '\\' + ' ' * (r_width - r_middle - 1)
        # 如果左子树高度小于右子树，高度对齐，左子树补充空行
        if l_height < r_height:
            l_lines += [' ' * l_width] * (r_height - l_height)
        # 如果右子树高度小于左子树，高度对齐，右子树补充空行
        elif r_height < l_height:
            r_lines += [' ' * r_width] * (l_height - r_height)
        # 合并左、右子树的行列表，每行之间加上当前节点的间隔
        merged_lines = [a + ' ' * width + b for a, b in zip(l_lines, r_lines)]
        # 返回完整的行列表，更新宽度和高度信息
        return [first_line, second_line] + merged_lines, l_width + width + r_width, max(l_height, r_height) + 2, l_width + width // 2

    # 情况 4：叶子节点（没有子节点）
    return [line], width, height, middle  # 返回节点值行，及其宽度和高度信息

# 示例：创建二叉树并打印
root = TreeNode(1)              # 根节点 1
root.left = TreeNode(2)         # 左子节点 2
root.right = TreeNode(3)        # 右子节点 3
root.left.left = TreeNode(4)    # 节点 2 的左子节点 4
root.left.right = TreeNode(5)   # 节点 2 的右子节点 5
root.right.right = TreeNode(6)  # 节点 3 的右子节点 6

display(root)  # 打印二叉树