###### tags: `Leetcode` `medium` `tree` `dfs` `python` `c++`

# 687. Longest Univalue Path

## [題目連結:] https://leetcode.com/problems/longest-univalue-path/

## 題目:
Given the ```root``` of a binary tree, return 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.

**The length of the path** between two nodes is represented by the number of edges between them.


## 解題想法:
* 此題為求最長的相同值路徑長度
* 不需一定要經由root算起
* 對於求樹相關的路徑問題: 往**遞迴思考**
* 需額外寫函式:
* def getPath(self,root):
* 求當前root所構成的最長相同路徑長度
* 為向下延伸的找長度，不能轉彎
* **Step1**: 對當前root左右節點分別遞迴求其最長相同路徑長度
* left=self.getPath(root.left)
* right=self.getPath(root.right)
* **Step2**: 判斷當前節點與左右子節點之關係
* 初始:
* lenOfLeft=0
* lenOfRight=0
* 若左子存在且root.val==root.left.val:
* lenOfLeft=left+1
* 若右子存在且root.val==root.right.val:
* lenOfRight=right+1
* **Step3**: 更新最終值與函式回傳值(**超重要易搞混**)
* 更新最終的res:
* **以當前root為中心可以彎曲+左+右**
* res=max(res, lenOfLeft+lenOfRight)
* 最終該getPath回傳值:
* 回傳是以該root為起點的長度，是要向下延伸
* 所以只能選左or右長的回傳
* return max(lenOfLeft, lenOfRight)

* 舉例case:

    此狀況 最長為2!!! 
             5
        5        6
    5       5   2   7

## Python:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)
        
class Solution(object):
    def longestUnivaluePath(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        self.res=0
        self.getPath(root)
        return self.res
    def getPath(self,root): #為向下延伸的 不能轉彎
        if not root:
            return 0
        left=self.getPath(root.left)
        right=self.getPath(root.right)
        lenOfLeft=0
        lenOfRight=0
        if root.left and root.left.val==root.val:
            lenOfLeft=left+1
        if root.right and root.right.val==root.val:
            lenOfRight=right+1
        #更新最大值  以該root為中心可以彎曲左+右
        self.res=max(self.res,lenOfLeft+lenOfRight)
        #但回傳以該root的長度 是要向下延伸 所以只能選左右長的回傳
        return max(lenOfLeft,lenOfRight)

root=TreeNode(5)
root.insertLeft(5)
root.insertRight(6)
root.left.insertLeft(5)
root.left.insertRight(5)
root.right.insertLeft(2)
root.right.insertRight(7)
root.printTree()

result=Solution()
ans=result.longestUnivaluePath(root)
print(ans) #2

## C++:

#include<bits/stdc++.h>
using namespace std;
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int longestUnivaluePath(TreeNode* root) {
        getPath(root);
        return res;
    }
    int getPath(TreeNode* root){
        if (!root)
            return 0;
        int left=getPath(root->left);
        int right=getPath(root->right);
        int lenOfLeft=0, lenOfRight=0;
        if (root->left && root->left->val==root->val)
            lenOfLeft=left+1;
        if (root->right && root->right->val==root->val)
            lenOfRight=right+1;
        res=max(res, lenOfLeft+lenOfRight);
        return max(lenOfLeft, lenOfRight);
    }

private:
    int res=0;
};