# 687. Longest Univalue Path

這題其實就是 base on&#x20;

543 Diameter of Binary Tree (post order

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

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

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

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2Fru4izcxKIdRHsRRIiPF4%2Fimage.png?alt=media\&token=801866e0-1f40-4a13-a5e5-75a3b4318ffb)

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

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

return max(left, right)+1

````java
```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)

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