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 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 private int maxLength = 0;
10
11 private int dfs(TreeNode node) {
12 if (node == null) return 0;
13 int leftPath = dfs(node.left);
14 int rightPath = dfs(node.right);
15 int left = 0, right = 0;
16 if (node.left != null && node.left.val == node.val) {
17 left = leftPath + 1;
18 }
19 if (node.right != null && node.right.val == node.val) {
20 right = rightPath + 1;
21 }
22 maxLength = Math.max(maxLength, left + right);
23 return Math.max(left, right);
24 }
25 public int longestUnivaluePath(TreeNode root) {
26 maxLength = 0;
27 dfs(root);
28 return maxLength;
29 }
30}This Java solution uses DFS to determine the longest univalue path length. It recursively calculates the path lengths and compares them to find the maximum.
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.
1import java.util.LinkedList;
This Java version employs a BFS strategy using a queue, iterating level by level to compute longest univalue paths and updating a maximum counter.