难度: Medium
Submission
运行时间: 48 ms
内存: 17.3 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def str2tree(self, s: str) -> Optional[TreeNode]:
if not s:
return None
num, stack = "", []
def generate_node():
node = TreeNode(int(num)) if num else None
if node:
if stack:
if stack[-1].left is None:
stack[-1].left = node
elif stack[-1].right is None:
stack[-1].right = node
stack.append(node)
for c in s:
if c != "(" and c != ")":
num += c
else:
generate_node()
num = ""
if c == ")":
stack.pop(-1)
return stack[0] if stack else TreeNode(int(s))
Explain
这个题解的思路是使用一个栈来模拟递归构建二叉树的过程。遍历字符串 s，遇到数字则累计存储，遇到左括号则根据累计的数字生成一个新节点，并将其加入栈中。如果栈顶节点的左子节点为空则将新节点作为左子节点，否则作为右子节点。遇到右括号则弹出栈顶节点。最后栈底元素即为构建出的二叉树的根节点。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def str2tree(self, s: str) -> Optional[TreeNode]:
if not s:
return None
num, stack = "", []
def generate_node():
# 根据累计的数字生成新节点
node = TreeNode(int(num)) if num else None
if node:
if stack:
if stack[-1].left is None:
stack[-1].left = node # 新节点作为左子节点
elif stack[-1].right is None:
stack[-1].right = node # 新节点作为右子节点
stack.append(node) # 新节点入栈
for c in s:
if c != "(" and c != ")":
num += c # 累计数字
else:
generate_node() # 遇到括号时根据累计数字生成新节点
num = "" # 数字累计清零
if c == ")":
stack.pop(-1) # 遇到右括号弹出栈顶节点
return stack[0] if stack else TreeNode(int(s))
Explore
在代码中，遍历字符串时使用一个变量`num`来累计每个字符。如果遇到的字符是数字（即不是左或右括号），则将该字符追加到`num`字符串的末尾。这样，遇到非数字字符时（左括号或右括号），`num`中存储的是完整的数字字符串，可以一次性转换为整数。此方法确保了即使是多位数也能被正确累积和转换。
在题解的实现中，如果字符串以数字结尾，`generate_node`并未在循环结束后显式调用。这可能会导致最后一个数字节点没有被创建。为了解决这个问题，可以在循环结束后检查`num`是否非空，如果非空，则需要调用`generate_node`来生成最后一个节点。这确保了所有的数字都能被转换为树节点，即使是在字符串的末尾。
在题解的逻辑中，遇到右括号时弹出栈顶元素是安全的。这是因为在之前的逻辑中，每当生成一个新的节点并且栈中已有其他节点时，新节点会被加入到栈顶节点的左或右子节点中。因此，当遇到一个右括号时，表示当前节点的所有子节点都已经处理完毕，可以安全地从栈中移除。
在当前题解的实现逻辑中，每个节点入栈时其左右子节点都是空的。新节点作为左子节点或右子节点的决定是在节点第一次加入栈时进行的。一旦一个节点的左右子节点都被赋值，它就会在遇到下一个右括号时被弹出栈。因此，不会出现栈顶节点左右子节点都不为空的情况，因为这样的节点不会再次遇到新节点需要连接的情况。