python O(n) solution -- reverse in order traversal while accumulating count

  • 0
    def convert_bst(root):
        accumulated_count = 0
        for node in in_order_reverse(root):
            accumulated_count += node.value
            node.value = accumulated_count
        return root
    def in_order_reverse(node):
        output = []
        for n in in_order_reverse_helper(node):
            output += n
        return output
    def in_order_reverse_helper(node):
            if node.right:
                yield in_order_reverse(node.right)
            yield [node]
            if node.left:
                yield in_order_reverse(node.left)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.