[LeetCode][Python3] 538. Convert BST to Greater Tree

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로 업데이트 해주면 된다.