27637: 括号嵌套二叉树

dfs, stack, http://cs101.openjudge.cn/practice/27637/

可以用括号嵌套的方式来表示一棵二叉树。

方法如下：*表示空的二叉树。

如果一棵二叉树只有一个结点，则该树就用一个非*字符表示，代表其根结点。

如果一棵二叉左右子树都非空，则用树根(左子树,右子树)的形式表示。树根是一个非*字符，左右子树之间用逗号隔开，没有空格。左右子树都用括号嵌套法表示。

如果左子树非空而右子树为空，则用树根(左子树,*)形式表示；如果左子树为空而右子树非空，则用树根(*,右子树)形式表示。

给出一棵树的括号嵌套表示形式，请输出其前序遍历序列、中序遍历序列、后序遍历序列。例如，A(B(*,C),D(E))表示的二叉树如图所示

输入

第一行是整数n表示有n棵二叉树(n<100) 接下来有n行，每行是1棵二叉树的括号嵌套表示形式

输出

对每棵二叉树，输出其前序遍历序列和中序遍历序列

样例输入

2
A
A(B(*,C),D(E,*))

样例输出

A
A
ABCDE
BCAED

来源

http://dsbpython.openjudge.cn/dspythonbook/P0680/

将输入的括号嵌套形式转换成二叉树，然后实现了前序和中序遍历。

python

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


def parse_tree(s):
    """ 解析括号嵌套格式的二叉树 """
    if s == '*':  # 处理空树
        return None
    if '(' not in s:  # 只有单个根节点
        return TreeNode(s)

    root_value = s[0]  # 根节点值
    subtrees = s[2:-1]  # 去掉根节点和外层括号

    # 使用栈找到逗号位置
    stack = []
    comma_index = None
    for i, char in enumerate(subtrees):
        if char == '(':
            stack.append(char)
        elif char == ')':
            stack.pop()
        elif char == ',' and not stack:
            comma_index = i
            break

    left_subtree = subtrees[:comma_index] if comma_index is not None else subtrees
    right_subtree = subtrees[comma_index + 1:] if comma_index is not None else None

    root = TreeNode(root_value)
    root.left = parse_tree(left_subtree)  # 解析左子树
    root.right = parse_tree(right_subtree) if right_subtree else None  # 解析右子树
    return root


def preorder_traversal(root):
    """前序遍历：根 -> 左 -> 右"""
    return root.value + preorder_traversal(root.left) + preorder_traversal(root.right) if root else ""


def inorder_traversal(root):
    """中序遍历：左 -> 根 -> 右"""
    return inorder_traversal(root.left) + root.value + inorder_traversal(root.right) if root else ""


# 读取输入
n = int(input().strip())  
results = []

for _ in range(n):
    tree_string = input().strip().replace(" ", "")  # 去掉可能的空格
    tree = parse_tree(tree_string)
    results.append(preorder_traversal(tree))
    results.append(inorder_traversal(tree))

print("\n".join(results))  # 按格式输出

优化版代码（精简高效 + O(n) 解析）

python

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


def parse_tree(s):
    """将括号嵌套形式解析为二叉树，使用流式指针解析避免重复切片"""
    i = 0
    n = len(s)

    def parse():
        nonlocal i
        if i >= n or s[i] == '*':
            i += 1  # 跳过空树符号
            return None

        node = TreeNode(s[i])
        i += 1

        if i < n and s[i] == '(':
            i += 1  # 跳过 '('
            node.left = parse()  # 左子树
            if i < n and s[i] == ',':
                i += 1  # 跳过 ','
                node.right = parse()  # 右子树
            if i < n and s[i] == ')':
                i += 1  # 跳过 ')'
        return node

    return parse()


def preorder(root):
    res = []
    def dfs(node):
        if not node: return
        res.append(node.val)
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return ''.join(res)


def inorder(root):
    res = []
    def dfs(node):
        if not node: return
        dfs(node.left)
        res.append(node.val)
        dfs(node.right)
    dfs(root)
    return ''.join(res)


# 主程序
if __name__ == "__main__":
    n = int(input().strip())
    for _ in range(n):
        s = input().strip().replace(" ", "")
        tree = parse_tree(s)
        print(preorder(tree))
        print(inorder(tree))

优点总结

优化项	原实现	优化后
解析复杂度	O(n²)（切片多次）	O(n)（指针推进）
递归逻辑	需要查找逗号、维护栈	自动语法驱动，简洁直观
拼接性能	字符串相加	`list.append + ''.join()`
可读性	多层嵌套逻辑	层次清晰、容易扩展

27637: 括号嵌套二叉树 ​

27637: 括号嵌套二叉树