###### tags: `LeetCode` `Recursion` `Tree` `Medium`
# LeetCode #687 [Longest Univalue Path](https://leetcode.com/problems/longest-univalue-path/)
### (Medium)
給定一個二元樹，找到最長的路徑，這個路徑中的每個節點具有相同值。這條路徑可以經過也可以不經過根節點。

注意：兩個節點之間的路徑長度由它們之間的邊數表示。

---
首先計算左右子樹的最長路徑, 接下來計算加上根節點之後的最長路徑(若左(右)節點的值與根結點相同, 則左(右)樹的最長路徑不變, 不同則歸零), 再來更新最長路徑(左樹路徑長+右樹路徑長+根結點), 最後回傳包含根節點的最長路徑(此時只能在左右子樹中選一個較長的)。

最後最長邊長為最長節點數減一。

---

class Solution {
public:
    int ans=0;
    int longestUnivaluePath(TreeNode* root) {
        if(!root)return 0;
        dfs(root);
        return ans-1;
    }
    int dfs(TreeNode* node){
        int l=node->left?dfs(node->left):0;
        int r=node->right?dfs(node->right):0;
        int ll=node->left&&node->left->val==node->val?l:0;
        int rr=node->right&&node->right->val==node->val?r:0;
        ans=max(ans, ll+rr+1);
        return 1+max(ll,rr);
    }
};