Skip to main content

538. Convert BST to Greater Tree

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

Python​

Inorder BST (First run)​

  • BST inorder is in increasing order
class Solution:
    def __init__(self):
        self.total = 0

    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return
        self.total = 0
        self._travel(root)

        return root

    def _travel(self, node):
        if not node:
            return

        self._travel(node.right)

        self.total += node.val
        node.val = self.total

        self._travel(node.left)

Inorder BST (second run)​

  • Use the Python nonlocal keyword
class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        total = 0

        def covert(node):
            nonlocal total

            if not node:
                return

            covert(node.right)

            total += node.val
            node.val = total

            covert(node.left)

        covert(root)
        return root