数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Python中从二叉树构建字符串
假设我们有一个二叉树，我们需要用括号和整数从二叉树中创建一个字符串，采用先序遍历的方式。空节点将用空的括号对“()”表示。我们需要省略所有不影响字符串和原始二叉树之间一对一映射关系的空括号对。
因此，如果输入是这样的：
那么输出将是 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 连接 '(' 连接 pot(node.right, 空字符串) 连接 ')'
- 返回 ss
- 在主方法中执行以下操作：
- 返回 pot(t, 空字符串)
让我们来看下面的实现来更好地理解：
示例
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)
更新于：2020年7月4日
751 次查看
广告