Leetcode - 687. Longest Univalue Path

---

tags: leetcode

687. Longest Univalue Path

https://leetcode.com/problems/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.
The length of path between two nodes is represented by the number of edges between them.

example 3:

      1
     / \
    1   1
   / \   \
  1  1    1
 /\        \
1 2         1

example 4:

    1
   / \
  1   1
 / \   \
1  1    1


[1 1 1 1 1 1]

1. 左邊的路徑、右邊的路徑
2. 路徑怎麼決定？
   如果能接過來（右邊的值＝當前的值）： 右邊的路徑＋1
   如果不能：0

Remark

http://www.csie.ntnu.edu.tw/~u91029/BinaryTree.html

# 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.ans=0
        def maxlength(node):
            if not node: return 0
            else: 
                left_node=node.left
                right_node=node.right
                left=maxlength(left_node)
                right=maxlength(right_node)
                if left_node and node.val==left_node.val:
                    mlength_left=left+1
                else:
                    mlength_left=0

                if right_node and node.val==right_node.val:
                    mlength_right=right+1
                else:
                    mlength_right=0
                self.ans=max(self.ans,mlength_right+mlength_left)
                return(max(mlength_right,mlength_left))
        
        maxlength(root)
        
        return self.ans