Given the root of a binary tree, return the length of the longest path, where each node in the path has the same value. This path may or may not pass through the root.
The length of the path between two nodes is represented by the number of edges between them.
Example 1:
Input: root = [5,4,5,1,1,null,5] Output: 2 Explanation: The shown image shows that the longest path of the same value (i.e. 5).
Example 2:
Input: root = [1,4,5,4,4,null,5] Output: 2 Explanation: The shown image shows that the longest path of the same value (i.e. 4).
Constraints:
[0, 104].-1000 <= Node.val <= 10001000.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.
This C solution defines a TreeNode structure and uses a depth-first search to calculate the longest univalue path at each node. We maintain a global variable to store the maximum path length globally.
C++
Java
Python
C#
JavaScript
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.
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.
This Java version employs a BFS strategy using a queue, iterating level by level to compute longest univalue paths and updating a maximum counter.
Python
C#
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.
| Approach | Complexity |
|---|---|
| Depth First Search (DFS) with Global Maximum | Time complexity: O(n), where n is the number of nodes in the tree, since we visit each node exactly once. |
| Breadth First Search for Tracking Paths | 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. |
Simplify Path - Stack - Leetcode 71 - Python • NeetCode • 73,047 views views
Watch 9 more video solutions →Practice Longest Univalue Path with our built-in code editor and test cases.
Practice on FleetCode