根据中缀表达式构造二叉表达式树

Submission

运行时间: 35 ms

内存: 0.0 MB

# Definition for a binary tree node.
# class Node(object):
#     def __init__(self, val=" ", left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def expTree(self, s: str) -> 'Node':
        
        # copied from discussion Two stacks approach
        ops, nums = [], []

        def mock_compute():
            op = ops.pop()
            r = nums.pop()
            l = nums.pop()
            nums.append(Node(val=op, left=l, right=r))

        for ch in s:
            if ch.isdigit():
                nums.append(Node(val=ch))
            elif ch in ['+', '-']:
                while ops and ops[-1] in ['+', '-', '*', '/']:
                    mock_compute()
                ops.append(ch)
            elif ch in ['*', '/']:
                while ops and ops[-1] in ['*', '/']:
                    mock_compute()
                ops.append(ch)
            elif ch == '(':
                ops.append(ch)
            elif ch == ')':
                while ops[-1] != '(':
                    mock_compute()
                ops.pop()
        while ops:
            mock_compute()
        return nums[0]

Explain

这个题解采用了两个栈（操作符栈 ops 和数字栈 nums）来处理并构造表达式树。数字栈用于存储表达式中的数字（或已构造的子表达式树），而操作符栈用于存储操作符。在遍历输入字符串 s 时，根据字符的类型（数字、操作符、括号）进行不同的操作： 1. 数字直接转换为树节点并压入 nums 栈。 2. 操作符 '+', '-' 时，如果 ops 栈顶的操作符为 '+', '-', '*', '/', 需要进行计算以保持操作符的优先级，然后将当前操作符压栈。 3. 操作符 '*', '/' 类似，但只比较栈顶是否为 '*', '/', 因为这两者优先级更高。 4. 左括号 '(' 直接压栈，表示优先级的提升。 5. 右括号 ')' 表示一个括号内的表达式结束，需要执行计算直到遇到左括号。遇到左括号后，将其出栈。 最后，如果操作符栈中还有剩余操作符，继续执行计算，直到栈为空。最终，nums 栈顶的节点即为根节点。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class Node(object):
#     def __init__(self, val=' ', left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def expTree(self, s: str) -> 'Node':
        ops, nums = [], [] # 操作符栈和数字栈
        def mock_compute():
            op = ops.pop() # 弹出操作符
            r = nums.pop() # 弹出右操作数
            l = nums.pop() # 弹出左操作数
            nums.append(Node(val=op, left=l, right=r)) # 构造节点并压栈
        for ch in s:
            if ch.isdigit():
                nums.append(Node(val=ch)) # 数字转为节点
            elif ch in ['+', '-']:
                while ops and ops[-1] in ['+', '-', '*', '/']:
                    mock_compute() # 处理优先级高或相等的操作符
                ops.append(ch)
            elif ch in ['*', '/']:
                while ops and ops[-1] in ['*', '/']:
                    mock_compute() # 处理优先级高的操作符
                ops.append(ch)
            elif ch == '(': # 处理左括号
                ops.append(ch)
            elif ch == ')': # 处理右括号
                while ops[-1] != '(': 
                    mock_compute() # 计算到左括号为止
                ops.pop() # 弹出左括号
        while ops:
            mock_compute() # 处理剩余的操作符
        return nums[0] # 返回表达式树的根节点

Explore

在处理操作符 '+' 和 '-' 时，需要考虑到 '+' 和 '-' 的优先级比 '*' 和 '/' 低。因此，如果栈顶含有任何操作符（包括 '+'、'-'、'*'、'/'），都可能需要先执行这些操作符，以确保表达式的计算顺序和优先级正确。而在处理 '*' 和 '/' 时，由于它们的优先级较高，仅当栈顶为 '*' 或 '/' 时，才需要执行 mock_compute，即处理其他同样优先级高的操作符，否则可以保留在栈中等待下一步操作。

题解中未直接处理多位数字的情况。在实际实现时，应当在遍历字符串时识别连续的数字字符。可以通过一个循环来读取完整的数字序列，直到遇到非数字字符，然后将读取到的完整数字转换为数值或节点。例如，使用一个临时变量存储数字字符串，当遇到非数字字符时，将这个字符串转换为数值，然后创建数值节点压入 nums 栈。

在遇到右括号 ')' 时，mock_compute 函数会循环执行，直到栈顶为左括号 '('。这确保了所有在括号内的操作符都会被处理。每遇到一个右括号，算法都会处理直到最近的一个左括号，因此嵌套的括号也能正确处理，每一对括号内的表达式都会在遇到其对应右括号时完全解决。左括号之后的操作符和数字都被视为括号内的一部分，直到遇到对应的右括号。

直接返回 nums 栈顶元素作为根节点通常是安全的，前提是输入字符串有效且至少包含一个数字。如果输入字符串为空或不包含任何数字（例如只有操作符或不匹配的括号），则 nums 栈可能为空。因此，在实际的代码实现中，应该加入检查确保 nums 栈不为空。如果输入字符串有效并且表达式正确解析，nums 栈的顶层元素应该是整个表达式的根节点。