# [Java/C++] Clean Code

1. `Longest-Univalue-Path` of a tree is among those `Longest-Univalue-Path-Across` at each node;
2. `Longest-Univalue-Path-Across` a node is sum of { `Longest-Univalue-Path-Start-At` each child with same value } + 1
3. Let an `dfs` to return `Longest-Univalue-Path-Start-At` each node, the `Longest-Univalue-Path-Across` `node` can be calculated by combine the `Longest-Univalue-Path-Start-At` of its 2 child; and we can use an global variable `res` to hold the max value and compare with each intermediate result.

Java

``````class Solution {
public int longestUnivaluePath(TreeNode root) {
int[] res = new int[1];
if (root != null) dfs(root, res);
return res[0];
}

private int dfs(TreeNode node, int[] res) {
int l = node.left != null ? dfs(node.left, res) : 0; // Longest-Univalue-Path-Start-At - left child
int r = node.right != null ? dfs(node.right, res) : 0; // Longest-Univalue-Path-Start-At - right child
int resl = node.left != null && node.left.val == node.val ? l + 1 : 0; // Longest-Univalue-Path-Start-At - node, and go left
int resr = node.right != null && node.right.val == node.val ? r + 1 : 0; // Longest-Univalue-Path-Start-At - node, and go right
res[0] = Math.max(res[0], resl + resr); // Longest-Univalue-Path-Across - node
return Math.max(resl, resr);
}
}
``````

C++

``````class Solution {
public:
int longestUnivaluePath(TreeNode* root) {
int lup = 0;
if (root) dfs(root, lup);
return lup;
}

private:
int dfs(TreeNode* node, int& lup) {
int l = node->left ? dfs(node->left, lup) : 0;
int r = node->right ? dfs(node->right, lup) : 0;
int resl = node->left && node->left->val == node->val ? l + 1 : 0;
int resr = node->right && node->right->val == node->val ? r + 1 : 0;
lup = max(lup, resl + resr);
return max(resl, resr);
}
};
``````

Varables
`l` is the length of single direction `Longest-Univalue-Path` start from `left-child`,
`r` is the length of single direction `Longest-Univalue-Path` start from `right-child`,
`resl` is the length of single direction `Longest-Univalue-Path` start from `parent` go left,
`resr` is the length of single direction `Longest-Univalue-Path` start from `parent` go right.
`int dfs(node)` returns the `Longest-Univalue-Path-Start-At` that `node`, and update the result of `Longest-Univalue-Path-Across` that `node` through side effect.
It is really hard to name those variables to reflect these concept.

Example:

``````                ...
/
4 (res = resl + resr = 3)
(resl = 2) / \ (resr= 1)
(l = 1) 4   4 (r = 0)
/
4
``````

resl is `Longest-Univalue-Path-Start-At` left node + 1,
resr is `Longest-Univalue-Path-Start-At` right node + 1,
in here the local result of `Longest-Univalue-Path-Across` at this node is the sum of the 2;

• @alexander Very concise!

• @alexander thanks for sharing, I came up with a very similar solution (https://discuss.leetcode.com/topic/105653/c-dfs-with-explanation), but I mis-understood the "path" requirement. For example, I thought the following use case should return 3, since there are 3 connections between these nodes with the same value:

``````    4
/
4
/ \
4   4
``````

However, the actual expected result from above use case is 2, since the "path" is expected to be a linear path ( i.e. NOT upside-down-Y shaped ). @administrators It would be great for above example to be added as a test case for this problem, since I kept failing test cases which were too large to be displayed as a tree, and I could not quickly find out that my understanding of this problem was incorrect.

• @alexander said in [Java/C++] Clean Code:

res[0] = Math.max(res[0], resl + resr);

@alexander why is res[0] = Math.max(res[0], resl + resr); required?

• @naveentrrko
resl is `Longest-Univalue-Path-Start-At` left node,
resr is `Longest-Univalue-Path-Start-At` right node,
in here the local result of `Longest-Univalue-Path-Across` at this node is the sum of the 2;

``````                ...
/
4 (res = resl + resr = 3)
(resl = 2) / \ (resr= 1)
(l = 1) 4   4 (r = 0)
/
4
``````

• ''return Math.max(resl, resr);''

I just wonder why you return the bigger one between the left result and the right result?

• @chen4393
`l` is the length of single direction `Longest-Univalue-Path` start from `left-child`,
`r` is the length of single direction `Longest-Univalue-Path` start from `right-child`,
`resl` is the length of single direction `Longest-Univalue-Path` start from `parent` go left,
`resr` is the length of single direction `Longest-Univalue-Path` start from `parent` go right.
`int dfs(node)` returns the `Longest-Univalue-Path-Start-At` that `node`, and update the result of `Longest-Univalue-Path-Across` that `node` through side effect.
It is really hard to name those variables to reflect these concept.

• @alexander forgive me, i am still not getting , why we should use "'return Math.max(resl, resr);" at all ?
isn't "lup = max(lup, resl+resr)" sufficient to check at each root ?

why to return max univaue path start at that node ?

• @alexander sorry .. got it..nice solution

• ``````class Solution {
int res = 0;
public int longestUnivaluePath(TreeNode root) {
helper(root, 0);
return res;
}
public int helper(TreeNode root, int path) {
if (root == null) {
return 0;
}
int left = helper(root.left, path);
int right = helper(root.right, path);
int sum = 0;
int cur = 0;
if (root.left != null && root.val == root.left.val) {
sum += left + 1;
cur = Math.max(cur, left + 1);
}
if (root.right != null && root.val == root.right.val) {
sum += right + 1;
cur = Math.max(cur, right + 1);
}
res = Math.max(res, sum);
return cur;
}
}
``````

• ``````static int lup(struct TreeNode* root, int *withMe) {
int lLongest, rLongest, longest, lWithMe, rWithMe;
if (!root)
return 0;
longest = lWithMe = rWithMe = 0;
lLongest = lup(root->left, &lWithMe);
rLongest = lup(root->right, &rWithMe);
if (root->left && root->left->val == root->val)
*withMe = longest = lWithMe + 1;
if (root->right && root->right->val == root->val) {
longest += rWithMe + 1;
*withMe = max2(*withMe, rWithMe + 1);
}
return max3(longest, rLongest, lLongest);
}

int longestUnivaluePath(struct TreeNode* root) {
int withMe;
return lup(root, &withMe);
}
``````

• @alexander I dont understand why define res like int[] res = new int[1];
Why i cant define the res like int res = 0; And i get the wrong result;

• @qianrenliang Because java does not support pass parameter by reference, the compiler actually make an copy for any parameter passed in, all you operation inside that method is actually on that copy, so once method return, the variable pass to the method is not changed.

``````    void foo(int i) {
int _i = i; // compiler implicitly make an copy on the input parameter
...
}
``````

• @alexander Thank you for your patient answer.

• @claytonjwong Your post just made me realize the same thing. They need to be more clear in their directions. I've been so confused as to why my code doesn't work... thanks!

• @FF_Ti
public int helper(TreeNode root, int path) don't see any usage for second parameter "path", I think it can be removed.

• @FF_Ti Hi, May I ask is here for every node, we add twice the same node because

for everynode, the max = left + right

right = length from child + 1

left = length from child + 1

Correct me if I am wrong

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.