Search

Increasing Order Search Tree

문제 설명 : 제공된 트리를 사용하여, val 값이 오름차순인 단방향 트리를 제작
풀이 방법
제공된 트리의 val 값을 오름차순으로 만들기 위해 중위 탐색으로 Node를 탐색 후 리스트에 순차적으로 저장하였다.
시간복잡도 : O(N)O(N)
성공 코드
# 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
복사