687._Longest_Univalue_Path.md

687. Longest Univalue Path

题目: https://leetcode.com/problems/longest-univalue-path/

难度:

Easy

思路

这道题也只能算个easy题目，根据传进来的root，我们只要从它的左右节点不停的递归下去，只要其value值与root一样， 该方向上的length就加1，最后我们将左右方向上的length相加, 递归取最大值

很重要的一点就是，Note: The length of path between two nodes is represented by the number of edges between them.

• 因此是self.res = max(self.res, left_arrow + right_arrow), return max(left_arrow, right_arrow)
• 而不是self.res = max(self.res, left_arrow + right_arrow + 1), return max(left_arrow + 1, right_arrow + 1)

# 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 dir_length(node):
            if not node:
                return 0
            left_len = dir_length(node.left)     # 左节点的length
            right_len = dir_length(node.right)   # 右节点的length
            left_dir, right_dir = 0, 0
            if node.left and node.left.val == node.val:
                left_dir = left_len + 1          # 当前节点的左节点方向的length
            if node.right and node.right.val == node.val:
                right_dir = right_len + 1        # 当前节点的右边节点方向的length
            self.res = max(self.res, left_dir + right_dir)
            return max(left_dir, right_dir)
        dir_length(root)
        return self.res