สมมติว่าเรามีไบนารีทรี เราต้องสร้างสตริงที่ประกอบด้วยวงเล็บและจำนวนเต็มจากไบนารีทรีที่มีวิธีการสั่งซื้อล่วงหน้า โหนด null จะแสดงด้วยวงเล็บที่ว่างเปล่า "()" และเราจำเป็นต้องละเว้นวงเล็บว่างทั้งหมดที่ไม่ส่งผลต่อความสัมพันธ์การแมปแบบหนึ่งต่อหนึ่งระหว่างสตริงกับไบนารีทรีเดิม
ดังนั้นหากอินพุตเป็นแบบ
จากนั้นผลลัพธ์จะเป็น 5(6()(8))(7)
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ตอบ :=สตริงว่าง
- กำหนดฟังก์ชัน pot() สิ่งนี้จะใช้โหนด s
- ถ้าเป็นโมฆะ
- คืนค่าสตริงว่าง
- ถ้าด้านซ้ายหรือด้านขวาของโหนดเป็นโมฆะ
- ส่งคืน node.data
- ss :=node.data
- ถ้า node.left ไม่ใช่ null แล้ว
- ss :=ss concatenate '(' concatenate pot(node.left, blank string) concatenate ')'
- มิฉะนั้น
- ss :=ss concatenate '()'
- ถ้า node.right ไม่เป็นโมฆะ
- ss :=ss concatenate '(' concatenate pot(node.right, blank string) concatenate ')'
- ส่งคืน ss
- จากวิธีหลัก ให้ทำดังนี้ -
- คืนหม้อ(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)
