实现二叉链类,完成以下功能: 根据括号表示法字符串构造二叉链 由二叉链输出二叉树(括号表示法) 翻转二叉树
时间: 2024-01-23 21:41:38 浏览: 69
好的,我理解你的问题了。以下是 Python 代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class BinaryTree:
def __init__(self):
self.root = None
def buildTree(self, s: str) -> TreeNode:
if not s:
return None
stack = []
for c in s:
if c == '(':
stack.append('(')
elif c == ')':
if stack:
stack.pop()
else:
return None
else:
num = ''
while c.isdigit():
num += c
if stack and stack[-1] == '-':
num = '-' + num
stack.pop()
c = s[len(num)]
node = TreeNode(int(num))
if stack:
parent = stack[-1]
if not parent.left:
parent.left = node
else:
parent.right = node
else:
self.root = node
stack.append(node)
if c == '-':
stack.append('-')
return self.root
def printTree(self, root: TreeNode) -> str:
if not root:
return ''
if not root.left and not root.right:
return str(root.val)
left = self.printTree(root.left)
right = self.printTree(root.right)
if root.right:
return str(root.val) + '(' + left + ')(' + right + ')'
else:
return str(root.val) + '(' + left + ')'
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
left = self.invertTree(root.left)
right = self.invertTree(root.right)
root.left = right
root.right = left
return root
```
其中,`buildTree` 方法通过栈实现解析括号表示法字符串并构造二叉链,`printTree` 方法则是根据二叉链输出括号表示法字符串。最后,`invertTree` 方法用来翻转二叉树。希望能够帮到你!
阅读全文