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

snoopybox 2018. 10. 7. 23:29

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