[Ruby] Two Lists


  • 0
    R
    def width_of_binary_tree(root)
        return 0 if root.nil?
        
        root.val = 0
        curr_nodes = [root]
        max_width = 0
        
        while(!curr_nodes.empty?) do
            max_width = [curr_nodes.last.val - curr_nodes.first.val + 1, max_width].max
            children = []
            curr_nodes.each do |node|
                if node.left
                    node.left.val = node.val * 2
                    children << node.left
                end
                if node.right
                    node.right.val = node.val * 2 + 1
                    children << node.right
                end
            end
            curr_nodes = children
        end
        
        max_width
    end
    

    The trick here is we want to find the min and max index of each level array to calculate that level's width. We do this by storing the index of each node into it's value. We multiply left by 2 and right by 2 + 1 (instead of the classic 2 + 1, 2 + 2 because we want each level array to start at 0.


Log in to reply
 

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