프로그래밍/LeetCode
[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로 업데이트 해주면 된다.