687. Longest Univalue Path

Information

  • Diffculty: Easy

  • Created: 2020-02-12 20:43:00

  • Last Motified: 2020-02-12 20:46:40

  • Tags: Tree, Recursion

Intuition

This is an simple problem. For each node, if its left node and right node has no same value as itself, then the longest path with its value in the sub-tree is 0. And other cases are just something very likely. So we could solve it recursivly.

Note that, for sub-tree with structure:

  4
 / \
4   4

When visiting the top 4 node, the total path would be right path length plus left path length plus 2.

Solution

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

class Solution:
    def longestUnivaluePath(self, root: TreeNode) -> int:
        return self._helper(root)[2]

    def _helper(self, node):
        if node is None:
            return None, 0, 0
        l = self._helper(node.left)
        r = self._helper(node.right)
        root = max(l[2], r[2])
        if l[0] == r[0] == node.val:
            non_root = max(l[1], r[1]) + 1
            root = max(l[1] + r[1] + 2, root)
        elif l[0] == node.val:
            non_root = l[1] + 1
        elif r[0] == node.val:
            non_root = r[1] + 1
        else:
            non_root = 0
        root = max(non_root, root)
        return node.val, non_root, root