在 Python 中从二叉树构造字符串
pythonserver side programmingprogramming更新于 2023/11/10 8:06:00
假设我们有一棵二叉树，我们必须从二叉树中以先序遍历的方式构造一个由括号和整数组成的字符串。空节点将由空括号对"()"表示。并且我们需要省略所有不影响字符串和原始二叉树之间一一映射关系的空括号对。
因此，如果输入如下
则输出为 5(6()(8))(7)
为了解决这个问题，我们将遵循以下步骤 −
- ans := 空白字符串
- 定义一个函数 pot()。这将获取节点 s
- 如果为空，则
- 返回空白字符串
- 如果节点的左侧或右侧为空，则
- 返回 node.data
- ss := node.data
- 如果 node.left 不为空，则
- ss := ss 连接 '(' 连接 pot(node.left, 空白字符串) 连接 ')'
- 否则，
- ss := ss 连接 '()'
- 如果 node.right 不为空，则
- ss := ss concatenate '(' concatenate pot(node.right, blank string) concatenate ')'
- return ss
- 从 main 方法执行以下操作 −
- return pot(t, blank string)
让我们看看下面的实现以便更好地理解 −
示例
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def insert(temp,data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
class Solution:
def tree2str(self, t: TreeNode):
ans = ''
def pot(node, s):
if node == None or node.data == 0:
return ''
if node.left == node.right == None:
return str(node.data)
ss = str(node.data)
if node.left != None:
ss = ss + '(' + pot(node.left, '') + ')'
else:
ss = ss + '()'
if node.right != None:
ss = ss + '(' + pot(node.right, '') + ')'
return ss
return pot(t, '')
ob = Solution()
root = make_tree([5,6,7,None,8])
print(ob.tree2str(root))
输入
[5,6,7,None,8]
输出
5(6()(8))(7)
