687.md

687. Longest Univalue Path

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

Note: The length of path between two nodes is represented by the number of edges between them.

Example 1:

Input:

              5
             / \
            4   5
           / \   \
          1   1   5
Output:

2
Example 2:

Input:

              1
             / \
            4   5
           / \   \
          4   4   5
Output:

2
Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

my thoughts:

1. travesal and pointer
   max = 0
   travesal from root to leaves
   when a node == node.child, length(node) = depth (node.child) + 1
   when a node == node.children, length(node) = depth(node.l) + 1 + depth(node.r)
   update max
   O(n*lgn)
   

******************** not done ********************* my solution:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def longestUnivaluePath(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.res = 0
        
        def dfs(n):
            if not n:
                return
            l = 0
            if n.left and n.val == n.left.val and n.right and n.val == n.right.val:
                # find the longest path via n, self.res = max( n & self.res )
                l = depth(n.left) + 2 + depth(n.right)
                
            if n.left and n.val == n.left.val and ( not n.right or n.val != n.right.val ):
                l = depth(n.left) + 1
                
            if n.right and n.val == n.right.val and ( not n.left or n.val != n.left.val ):
                l = depth(n.right) + 1
                
            self.res = max( self.res, l )
            dfs(n.left)
            dfs(n.right)
                
        def depth(n):
            if not n:
                return 0
            if not n.left and not n.right:
                return 0
            left = right = 0
            if n.left and n.val == n.left.val:
                left = depth(n.left) + 1
            if n.right and n.val == n.right.val:
                right = depth(n.right) + 1
            return max (left, right)
        
        dfs(root)
        return self.res

my comments: solution accepted, 1138ms run time, one of the worst... from other ppl's solution:

1. The fastest python submission so far (532ms):

class Solution(object):
    def longestUnivaluePath(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        
        longpaths = []
        
        def getLongest(node, parent_val):
            if node is None: return 0
            if node.val == parent_val:
                return (max(getLongest(node.left, node.val), getLongest(node.right, node.val)) + 1)
            else:
                longpaths.append(getLongest(node.left, node.val) 
                                 + getLongest(node.right, node.val))
                return 0
        getLongest(root, None)
        return max(longpaths) if longpaths else 0

readable and elegent. definitely an awesome perspective: each node either equals to or not equals to its parent, if yes, and only when yes, the length will grow by 1; if no, and when recursion is done it will be no, return 0