•
문제 링크 : leetcode.com
•
문제 설명 : 제공된 트리를 사용하여, val 값이 오름차순인 단방향 트리를 제작
•
풀이 방법
◦
제공된 트리의 val 값을 오름차순으로 만들기 위해 중위 탐색으로 Node를 탐색 후 리스트에 순차적으로 저장하였다.
•
시간복잡도 :
•
성공 코드
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def increasingBST(self, root: TreeNode) -> TreeNode:
search_stack = []
self.search_tree(root, search_stack)
# 중위탐색을 진행한 Node를 사용하여 right만 존재하는 단일 트리 제작
for i in range(len(search_stack)-1):
search_stack[i].right = search_stack[i + 1]
# 첫 Node 반환
return search_stack[0]
def search_tree(self, node, search_stack):
# 왼쪽 노드 탐색
if node.left:
self.search_tree(node.left, search_stack)
node.left = None
# 중앙 노드(현 노드)추가
search_stack.append(node)
# 우측 노드 탐색
if node.right:
self.search_tree(node.right, search_stack)
Python
복사
