687. Longest Univalue Path

class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def longestUnivaluePath(self, root): return self.longestHelper(root)[0] def longestHelper(self, root): # this function returns both the value and whether include_root = True if root == None: val = 0 include_root = False elif (root.left == None and root.right == None): # leaf node val = 1 include_root = True else: if root.val == root.left.val: # current node val = left child val if longestHelper(root.left)[1] == True: # left child in its longest path lmax = longestHelper(root.left)[0] + 1 linclude = True else: # left child not in its longest path if longestHelper(root.left)[0] <= 2: # left child longest path shorter than left child + current node lmax = 2 # update to left child + current node linclude = True else: lmax = longestHelper(root.left)[0] linclude = False else: # current node val != left child val if longestHelper(root.left)[0] <= 1: lmax = 1 # use current node linclude=True else: lmax = longestHelper(root.left)[0] linclude = False # repeat the process on right child if root.val == root.right.val: # current node val = right child val if longestHelper(root.right)[1] == True: # right child in its longest path rmax = longestHelper(root.right)[0] + 1 rinclude = True else: # right child not in its longest path if longestHelper(root.right)[0] <= 2: # right child longest path shorter than right child + current node rmax = 2 # update to right child + current node rinclude = True else: rmax = longestHelper(root.right)[0] rinclude = False else: # current node val != right child val if longestHelper(root.right)[0] <= 1: rmax = 1 # use current node rinclude=True else: rmax = longestHelper(root.right)[0] rinclude = False # compare right and left if rmax >= lmax: return [rmax, rinclude] else: return [lmax, linclude]