687. Longest Univalue Path

這題其實就是 base on

543 Diameter of Binary Tree (post order

https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-66994/dong-ge-da-334dd/

再加上要檢查 prev val 一樣就可以

因為最長的 path 有可能出現在有個轉折的這裡

所以求左＋右 最大 Math.max(left+right, result)

但最後 （當前結果包含本身的點, 不是 path

return max(left, right)+1

```java
class Solution {
    int result = 0;
    public int longestUnivaluePath(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        dfs(root, root.val);
        return result;
    }
    private int dfs(TreeNode node, int prev) {
        if (node == null) {
            return 0;
        }
        int left = dfs(node.left, node.val);
        int right = dfs(node.right, node.val);
        result = Math.max(result, left + right);
        if (node.val == prev) {
            return Math.max(left, right) + 1;
        }
        return 0; // node.val != prev
    }
}
```

以下這做法是以求節點(加上那個拐點)的角度去看的...所以+1

但最後-1

T: O(n)

S: O(h), worst O(n)

class Solution {
    int res = 0;
    public int longestUnivaluePath(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root);
        return res-1;
    }
    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int len1 = dfs(root.left);
        int len2 = dfs(root.right);
        
        int left = 0;
        int right = 0;
        if (root.left != null && root.val == root.left.val) {
            left = len1;
        }
        if (root.right != null && root.val == root.right.val) {
            right = len2;
        }
        res = Math.max(res, left+right+1);
        return Math.max(left, right)+1;
    }
}