이진 트리가 있다고 가정해 봅시다. 문자열을 괄호와 정수로 구성해야 하며, 사전 순서 순회 방식을 사용하는 이진 트리의 정수로 구성되어야 합니다. null 노드는 빈 괄호 쌍 "()"으로 표시됩니다. 그리고 문자열과 원래 바이너리 트리 간의 일대일 매핑 관계에 영향을 주지 않는 모든 빈 괄호 쌍을 생략해야 합니다.
따라서 입력이 다음과 같으면
그러면 출력은 5(6()(8))(7)
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- ans :=빈 문자열
- pot() 함수를 정의합니다. 노드가 필요합니다. s
- 가 null이면
- 빈 문자열 반환
- 노드의 왼쪽 또는 오른쪽이 null이면
- node.data 반환
- ss :=node.data
- node.left가 null이 아니면
- ss :=ss 연결 '(' 연결 pot(node.left, 공백 문자열) 연결 ')'
- 그렇지 않으면
- ss :=ss 연결 '()'
- node.right가 null이 아니면
- ss :=ss 연결 '(' 연결 포트(node.right, 공백 문자열) 연결 ')'
- 반환
- 메인 방법에서 다음을 수행하십시오 -
- 반환 포트(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)