2017 年第 41 题

题目描述

给定一棵表达式树，叶结点存放操作数，非叶结点存放运算符。请按中缀表达式形式输出该表达式，并根据需要添加括号，使原树结构能够被唯一表示。

解题思路

表达式树的中缀输出规律很直接：

1. 递归输出左子树。
2. 输出根结点。
3. 递归输出右子树。

难点在括号。

为了保证原结构不丢失，可以对每个非叶子子树加一层括号。常见写法是：

• 叶结点直接返回其值。
• 非叶结点返回 "(" + 左子树 + 根 + 右子树 + ")"。
• 最外层根结点的括号最后再去掉。

手算示例

表达式树：

        *
      /   \
     +     -
    / \   / \
   a   b c   d

递归过程：

左子树：(+ a b) -> (a+b)
右子树：(- c d) -> (c-d)
根结点：((a+b)*(c-d))

去掉最外层括号：
(a+b)*(c-d)

Python 实现

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


def infix_expression(root):
    def dfs(node, is_root=False):
        if node.left is None and node.right is None:
            return str(node.val)

        left = dfs(node.left)
        right = dfs(node.right)
        expr = f"{left}{node.val}{right}"
        return expr if is_root else f"({expr})"

    if root is None:
        return ""
    return dfs(root, True)

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(h)，h 为树高

易错点

• 叶结点不能再套括号，否则结果会显得冗余。
• 最外层括号通常需要去掉。
• 如果真题采用数组三元组存储，递归前先根据下标找到左右孩子。

对应题

来源	题目	相似度	主要差异
PAT 甲级	1130 Infix Expression	90%	真题常见写法为数组静态存储

难度

⭐️⭐️⭐️