Ruby solution using BFS, recursion


  • 0
    S
    def longest_univalue_path(root)
        
        return 0 if !root
        
        node = root
        queue = []
        queue.push(node)
        max = 0
    
        while !queue.empty?
            deq = queue.shift
            
            left_path_l = 0
            right_path_l = 0
            sum = 0
            
            if deq.left
                left_path_l = longest_univalue_path_helper(deq.left, deq)
                queue.push(deq.left)
            end
            
            if deq.right
                right_path_l = longest_univalue_path_helper(deq.right, deq) if deq.right
                queue.push(deq.right)
            end
    
            
            sum = left_path_l + right_path_l
            
            max = sum if sum > max
            
                    
        end
        
        max
    end
    
    def longest_univalue_path_helper(node, parent)
        return 0 if node.val != parent.val
        
        left_same_count = node.left ? longest_univalue_path_helper(node.left, node) : 0
        right_same_count = node.right ? longest_univalue_path_helper(node.right, node) : 0
         
        left_same_count > right_same_count ? left_same_count + 1 : right_same_count + 1
    end
    
    

Log in to reply
 

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