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.
1#include <iostream>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11class Solution {
12public:
13 int maxLength = 0;
14 int dfs(TreeNode* node) {
15 if (!node) return 0;
16 int leftPath = dfs(node->left);
17 int rightPath = dfs(node->right);
18 int left = 0, right = 0;
19 if (node->left && node->left->val == node->val) {
20 left = leftPath + 1;
21 }
22 if (node->right && node->right->val == node->val) {
23 right = rightPath + 1;
24 }
25 maxLength = max(maxLength, left + right);
26 return max(left, right);
27 }
28 int longestUnivaluePath(TreeNode* root) {
29 maxLength = 0;
30 dfs(root);
31 return maxLength;
32 }
33};This C++ solution uses a TreeNode structure and a class Solution. We perform a DFS traversal, calculating the longest univalue path at each step and update the global maximum univalue path length.
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.