[파이썬 알고리즘 인터뷰][BST] 이진 탐색 트리를 더 큰 수 합게 트리로

[파이썬 알고리즘 인터뷰][BST] 이진 탐색 트리를 더 큰 수 합게 트리로

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다.

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

문제 정의

노드의 값을 현재 노드의 값보다 큰 모든 노드의 값의 합으로 변경

책에서 구현된 코드

class Solution: val: int = 0 def bstToGst(self, root: TreeNode) -> TreeNode: # 중위 순회 노드 값 누적 if root: self.bstToGst(root.right) self.val += root.val root.val = self.val self.bstToGst(root.left) return root

기억해야할 기법

구현보다 활용이 더 어려울듯

문제를 트리로 전환하여 떠올리는 것 문제의 요구사항을 그림으로 떠올리는 것 그 그림이 중위순회를 의미한다는 것을 캐치하는 것

내가 구현한 코드

class Solution: sum = 0 def bstToGst(self, root: TreeNode) -> TreeNode: if root: self.bstToGst(root.right) root.val = self.sum = self.sum + root.val self.bstToGst(root.left) return root

책에서 구현한 코드와 같다

from http://pythaac.tistory.com/123 by ccl(A) rewrite - 2021-08-04 16:00:37