## Friday, May 4, 2018

### LeetCode 687 - Longest Univalue Path

https://leetcode.com/problems/longest-univalue-path/description/
Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.
Note: The length of path between two nodes is represented by the number of edges between them.
Example 1:
Input:
```              5
/ \
4   5
/ \   \
1   1   5
```
Output:
```2
```
Example 2:
Input:
```              1
/ \
4   5
/ \   \
4   4   5
```
Output:
```2
```
Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

We can think of any path (of nodes with the same values) as up to two arrows extending from it's root.
Specifically, the root of a path will be the unique node such that the parent of that node does not appear in the path, and an arrow will be a path where the root only has one child node in the path.
Then, for each node, we want to know what is the longest possible arrow extending left, and the longest possible arrow extending right? We can solve this using recursion.
Algorithm
Let `arrow_length(node)` be the length of the longest arrow that extends from the `node`. That will be `1 + arrow_length(node.left)` if `node.left` exists and has the same value as `node`. Similarly for the `node.right` case.
While we are computing arrow lengths, each candidate answer will be the sum of the arrows in both directions from that node. We record these candidate answers and return the best one.

int ans;
public int longestUnivaluePath(TreeNode root) {
ans = 0;
arrowLength(root);
return ans;
}
public int arrowLength(TreeNode node) {
if (node == null) return 0;
int left = arrowLength(node.left)
int right = arrowLength(node.right);
int arrowLeft = 0, arrowRight = 0;
if (node.left != null && node.left.val == node.val) {
arrowLeft += left + 1;
}
if (node.right != null && node.right.val == node.val) {
arrowRight += right + 1;
}
ans = Math.max(ans, arrowLeft + arrowRight);
return Math.max(arrowLeft, arrowRight);
}

https://leetcode.com/problems/longest-univalue-path/discuss/108136/JavaC++-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.
`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

``````    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);
}``````