1038. Binary Search Tree to Greater Sum Tree
링크
https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/
문제 설명
Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.
As a reminder, a binary search tree is a tree that satisfies these constraints:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
제약 조건
The number of nodes in the tree is in the range [1, 100].
0 <= Node.val <= 100
All the values in the tree are unique.
코드
# 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 __init__(self):
self.array=[]
self.sum=0
def travel(self,current:TreeNode):
if current==None:
return
else:
self.travel(current.left)
self.array.append(current.val)
self.sum+=current.val
self.travel(current.right)
def make(self,current:TreeNode,sums_dict:dict):
if current==None:
return
else:
self.make(current.left,sums_dict)
current.val=sums_dict[current.val]
self.make(current.right,sums_dict)
def bstToGst(self, root: TreeNode) -> TreeNode:
self.travel(root)
previous_sum=self.sum
sums=0
sums_dict=dict()
for i in range(len(self.array)):
if self.array[i] not in sums_dict:
sums_dict[self.array[i]]=-1
sums_dict[self.array[i]]=previous_sum
sums+=self.array[i]
previous_sum=self.sum-sums
self.make(root,sums_dict)
return root
해설
-
중위 순회를 이용하여 이진트리를 정렬된 배열로 만든다.
위 그림의 예를 들면, 중위 순회의 결과로 [0,1,2,3,4,5,6,7,8]
이 나온다.
-
합의 차이를 구해놓고, 딕셔너리에 담는다. All the values in the tree are unique. 라는 조건이 있으므로 딕셔너리를 사용하면 효율적이다. 왜냐하면 유일한 (키-밸류)쌍의 해시의 조회속도는 O(1)이기 때문이다.
-
다시 중위 순회를 하되, 이번엔 2.에서 만든 딕셔너리를 이용하여 값을 갱신한다.
Author And Source
이 문제에 관하여(1038. Binary Search Tree to Greater Sum Tree), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@dasd412/1038.-Binary-Search-Tree-to-Greater-Sum-Tree
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
# 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 __init__(self):
self.array=[]
self.sum=0
def travel(self,current:TreeNode):
if current==None:
return
else:
self.travel(current.left)
self.array.append(current.val)
self.sum+=current.val
self.travel(current.right)
def make(self,current:TreeNode,sums_dict:dict):
if current==None:
return
else:
self.make(current.left,sums_dict)
current.val=sums_dict[current.val]
self.make(current.right,sums_dict)
def bstToGst(self, root: TreeNode) -> TreeNode:
self.travel(root)
previous_sum=self.sum
sums=0
sums_dict=dict()
for i in range(len(self.array)):
if self.array[i] not in sums_dict:
sums_dict[self.array[i]]=-1
sums_dict[self.array[i]]=previous_sum
sums+=self.array[i]
previous_sum=self.sum-sums
self.make(root,sums_dict)
return root
-
중위 순회를 이용하여 이진트리를 정렬된 배열로 만든다.
위 그림의 예를 들면, 중위 순회의 결과로[0,1,2,3,4,5,6,7,8]
이 나온다. -
합의 차이를 구해놓고, 딕셔너리에 담는다. All the values in the tree are unique. 라는 조건이 있으므로 딕셔너리를 사용하면 효율적이다. 왜냐하면 유일한 (키-밸류)쌍의 해시의 조회속도는 O(1)이기 때문이다.
-
다시 중위 순회를 하되, 이번엔 2.에서 만든 딕셔너리를 이용하여 값을 갱신한다.
Author And Source
이 문제에 관하여(1038. Binary Search Tree to Greater Sum Tree), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dasd412/1038.-Binary-Search-Tree-to-Greater-Sum-Tree저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)