687. Longest Univalue Path

"""
687. Longest Univalue Path
http://www.cnblogs.com/grandyang/p/7636259.html
"""
class Solution(object):
    def __init__(self):
        self.res = 0

    def helper(self, node):
        if not node:   # 递归的基本条件是 当root为空时，返回0到上一层
            return 0

        left = self.helper(node.left)           # 首先，对其左右节点调用递归函数。得到其左右子树的最大相同路径长度。
        right = self.helper(node.right)

        # 现在左右子树要与 根节点 组成path
        if node.left and node.val == node.left.val: # 如果，左子树存在并且左子树的val == root的value，那么左子树的最大相同路径+1
            left += 1
        else:                                       # 如果，左子树不存在或者左子树的val ！= root的value, 那么左子树的最大相同路径为0
            left = 0

        if node.right and node.val == node.right.val:
            right += 1
        else:
            right = 0

        self.res = max(self.res, left + right)      # 如果，与根节点组成path以后的值大于 res 那么就更新 res

        return max(left, right)             # 返回的是以该结点为终点的最长路径长度，这样回溯的时候，我们还可以继续连上其父结点

    def longestUnivaluePath(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.helper(root)
        return self.res