Longest Univalue Path LeetCode solution in C++

1
class Solution {
2
 public:
3
  int maxlen = 0;
4
  pair<int, int> util(TreeNode *root, int val) {
5
    if (!root) return {0, -1001};
6

7
    // in pair we will the first part will return the no nodes ,
8
    // and in the second part we will return the value associated with it
9

10
    pair<int, int> l = util(root->left, root->val);
11
    pair<int, int> r = util(root->right, root->val);
12

13
    /* now we will check whether the value coming from
14
    the left subtree or(&) right subtree is equal to the
15
    value of the current node
16

17
     if equal to both the left && right subtree, then the length returned
18
    will be max of the left & right subtree , becuase ATQ, we have to
19
    return the longest path where each node in the path has the same
20
    value , therefore from the current node we can travel to either the
21
    left or right subtree , but the maxlength can be l.first+r.first+1 ,
22
    because we can travel from the leftmost node through the current
23
    node to the rightmost node , which will be a valid path , therefore
24
    we will compare this with the maxlength
25

26
    */
27
    if (l.second == root->val && r.second == root->val) {
28
      maxlen = max(maxlen, l.first + r.first + 1);
29
      return {max(l.first, r.first) + 1, root->val};
30

31
    }
32

33
    // now similary checking for all the other nodes:
34

35
    else if (l.second == root->val) {
36
      maxlen = max(maxlen, l.first + 1);
37
      return {l.first + 1, root->val};
38
    } else if (r.second == root->val) {
39
      maxlen = max(maxlen, r.first + 1);
40
      return {r.first + 1, root->val};
41
    } else {
42
      return {1, root->val};
43
    }
44
  }
45
  int longestUnivaluePath(TreeNode *root) {
46
    if (!root) return 0;
47
    util(root, root->val);
48
    return max(maxlen - 1, 0);
49
  }
50
};