Problem :

https://leetcode.com/problems/convert-bst-to-greater-tree/description/


My Solution :

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def __init__(self):
self.total = 0

def convertBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root:
self.convertBST(root.right)
self.total += root.val
root.val = self.total
self.convertBST(root.left)
return root


Comment :

BST이기 때문에 right, root, left 순서로 순회하면 내림차순으로 방문하게 된다. 따라서 누적 합을 계속해서 root.val로 업데이트 해주면 된다.