Given the root of a binary tree, find the length of the longest univalue path. An univalue path is a path between any two nodes where all the nodes have the same value. The length of the path is the number of edges.
The last example is a good one. Same value nodes can only connect in one direction but not both.
Analysis
Divide and conquer is build for these path related problems. The return type needs to hold a couple info including the longest univalue path so far, the current univalue path, and the current value.
Code
class Solution:
class ResultType:
def __init__(self, curVal, curLen, maxLen):
self.curVal = curVal
self.curLen = curLen
self.maxLen = maxLen
def longestUnivaluePath(self, root: TreeNode) -> int:
if root is None:
return 0
return self.pathHelper(root).maxLen - 1
def pathHelper(self, node: TreeNode) -> ResultType:
# base
if node is None:
return self.ResultType(None, 0, 0)
# divide
leftTree = self.pathHelper(node.left)
rightTree = self.pathHelper(node.right)
# merge
# compute current length
curLen = 1
combinedLen = 1
if leftTree.curVal == node.val:
curLen = max(curLen, leftTree.curLen + 1)
combinedLen += leftTree.curLen
if rightTree.curVal == node.val:
curLen = max(curLen, rightTree.curLen + 1)
combinedLen += rightTree.curLen
# compute max length
maxLen = max(combinedLen, leftTree.maxLen, rightTree.maxLen)
return self.ResultType(node.val, curLen, maxLen)
