Sponsored
Sponsored
This approach utilizes a post-order traversal (DFS) to explore all nodes of the binary tree. For each node, we calculate the univalue path length for both the left and right subtrees. We update the global maximum univalue path length during the traversal. The key idea is to compute the longest path length for each node based on whether its children have the same value.
Time complexity: O(n), where n is the number of nodes in the tree, since we visit each node exactly once.
Space complexity: O(h), where h is the height of the tree. This space is used by the recursion stack.
1class TreeNode:
2 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7class Solution:
8 def __init__(self):
9 self.maxLength = 0
10
11 def dfs(self, node):
12 if not node:
13 return 0
14 leftPath = self.dfs(node.left)
15 rightPath = self.dfs(node.right)
16 left = right = 0
17
18 if node.left and node.left.val == node.val:
19 left = leftPath + 1
20 if node.right and node.right.val == node.val:
21 right = rightPath + 1
22
23 self.maxLength = max(self.maxLength, left + right)
24 return max(left, right)
25
26 def longestUnivaluePath(self, root):
27 self.maxLength = 0
28 self.dfs(root)
29 return self.maxLengthThe Python solution defines a TreeNode class and a Solution class. It uses a DFS approach to explore each node's left and right path lengths, updating a global maximum length variable.
This approach uses the Breadth First Search (BFS) method to traverse the tree level by level. As we traverse each level, we compute the longest univalue paths extending from the current node. The maximum path length is globally tracked using a queue to manage the current node and its depth in the tree.
Time complexity: O(n^2) in the worst case due to nested calls to traverse each node and its children. However, can perform better on average.
Space complexity: O(n) for managing the queue size in the same level.
1from collections import deque
2
3
Using Python and a dequeue implementation, this solution employs BFS for calculating longest univalue paths, maintaining a global maximum.