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 constructor(val) {
3 this.val = val;
4 this.left = this.right = null;
5 }
6}
7
8var longestUnivaluePath = function(root) {
9 let maxLength = 0;
10
11 const dfs = (node) => {
12 if (!node) return 0;
13 const leftPath = dfs(node.left);
14 const rightPath = dfs(node.right);
15 let left = 0, right = 0;
16
17 if (node.left && node.left.val === node.val) {
18 left = leftPath + 1;
19 }
20 if (node.right && node.right.val === node.val) {
21 right = rightPath + 1;
22 }
23 maxLength = Math.max(maxLength, left + right);
24 return Math.max(left, right);
25 };
26
27 dfs(root);
28 return maxLength;
29};This JavaScript solution defines a TreeNode class and uses a DFS approach within the function to compute the longest univalue path, updating a global maximum path 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.
1using System.Collections.Generic;
2
3public class TreeNode {
4 public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public int LongestUnivaluePath(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
int maxLength = 0;
while (queue.Count > 0) {
TreeNode node = queue.Dequeue();
int leftLength = node.left != null && node.left.val == node.val ? LongestPathFromNode(node.left) + 1 : 0;
int rightLength = node.right != null && node.right.val == node.val ? LongestPathFromNode(node.right) + 1 : 0;
maxLength = Math.Max(maxLength, leftLength + rightLength);
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
return maxLength;
}
private int LongestPathFromNode(TreeNode node) {
if (node == null) return 0;
int leftPath = node.left != null && node.left.val == node.val ? LongestPathFromNode(node.left) + 1 : 0;
int rightPath = node.right != null && node.right.val == node.val ? LongestPathFromNode(node.right) + 1 : 0;
return Math.Max(leftPath, rightPath);
}
}A C# solution employs a queue for BFS traversal, exploring each layer for univalue path lengths and accumulating the path length if values match the root.