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.
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.