univalue.rb

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end

=begin

1. Understand the problem
2. Manually work on the given examples and see how you can compute the value
3. From the perspective of the root, I have to find the max of
left subtree's value and right subtree's value
4. Longest path may or may not go through the root
5. Define terms in the problem statement
    All the nodes in the path must be of the same value
    Identify the invariant
6. Recursive approach.
    Base cases:
       N = 0
       N = 1
       
       result = 0
       
       Minimize the number of cases
       We can one base case where N = 0
       When you have only one node, or reach a leaf node
         You are handling them in the same way
        
       N = 2
       The node values are the same
       result = 1
       
       The node values are NOT the same
       result = 0
       
       N = 3
       The node values are the same
       result = 2
       
       The node values are NOT the same
       result = 0
    
    What is the unit of work?
      - My left child and right child values are the same as my value
         so the result = 2
    
    What is the role of a leaf node?
        Defines the base case
    What is the role of an intermediate node?
    
    What is my responsibility as an intermediate node?
    Should I return a value?
    
    How are we dealing with leaf nodes?
      - Special case - we hit the base case
      - left child - 0
      - right child - 0
      
    Recursive cases:
    Problem Decomposition
     - left subtree
     - right subtree
   
   We need do the unit of work after the recursive calls
    
  1. How do we keep track of different lengths?
  2. How do we keep updating the max values?
        max variable ?
  3.   
  
  

=end

@max = 0

def univalue_path(root)
  if root.nil?
      return 0
  end
  
  left = univalue_path(root.left)
  right = univalue_path(root.right)
   
   left_edge = 0 
    right_edge = 0
#  If I have a left child then I will check if my value is same my left child value
  if root.left and root.val == root.left.val
      left_edge = left + 1
  end
    
  if root.right and root.val == root.right.val
     right_edge = right + 1
  end
     
  @max = [@max, left_edge + right_edge].max
end

# @param {TreeNode} root
# @return {Integer}
def longest_univalue_path(root)
  univalue_path(root)
    @max
end