資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告