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


  • 0
    E
    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.