0536：从字符串生成二叉树（★）

力扣第 536 题

题目

你需要用一个包括括号和整数的字符串构建一棵二叉树。

输入的字符串代表一棵二叉树。它包括整数和随后的 0 、1 或 2 对括号。整数代表根的值，一对括号内表示同样结构的子树。

若存在子结点，则从左子结点开始构建。

示例 1:

输入： s = "4(2(3)(1))(6(5))"
输出： [4,2,6,3,1,5]

示例 2:

输入： s = "4(2(3)(1))(6(5)(7))"
输出： [4,2,6,3,1,5,7]

示例 3:

输入： s = "-4(2(3)(1))(6(5)(7))"
输出： [-4,2,6,3,1,5,7]

提示：

• 0 <= s.length <= 3 * 104
• 输入字符串中只包含 '(', ')', '-' 和 '0' ~ '9'
• 空树由 "" 而非"()"表示。

分析

正则提取出值和括号，然后用栈模拟递归即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def str2tree(self, s: str) -> TreeNode:
	stack = []
	for val, right in re.findall('(-?\d+)|(\))', s):
		if val:
			stack.append(TreeNode(int(val)))
		else:
			x = stack.pop()
			if not stack[-1].left:
				stack[-1].left = x
			else:
				stack[-1].right = x
	return stack[0] if stack else None

60 ms