# 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:
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
자신보다 같거나 큰 값을 구하려면 자기 자신을 포함한 우측 자식 노드의 합을 구하면 된다.
<더 큰 수 합계 트리를 위한 탐색 순서>
오른쪽-부모-왼쪽
순으로 이어지며, 오른쪽 자식부터 운행하는 중위 순회(In-Order)에 해당됨을 알 수 있다. self.val
은 지금까지 누적된 값이고, root.val
은 현재 노드의 값이다.
최초 self.val
은 클래스 멤버 변수로 선언하고 0이 되도록 직관적으로 선언했다.
root
가 있을 때만 처리되게 했으며, root.val
을 조작한 이후에는 다시 root
를 리턴한다.
root
를 리턴하지 않아도 관계 없다. 재귀 호출 시 리턴 값은 사용하지 않기 때문이다.
파이썬은 모든 변수가 참조이기 때문에, 객체 내부의 값을 변경하면 해당 객체를 가리키는 모든 변수는 자연스럽게 따라서 값이 변한다.
리트코드는 아마 호출 시 root = solution.bstToGst(root)
와 같은 형태로 리턴 값을 받아오도록 구현되어 있을 것이다.
이때 리턴 값을 돌려주지 않으면 root
는 None
이 되어 버린다.
리트코드에서 리턴 값을 주지 않으면 정답이 출력되지 않는 것도 그 때문일 것이다.
따라서 반드시 return root
를 명시한다.